题解：UVA1672 不相交的正规表达式 Disjoint Regular Expressions
爆肝两天+中间的夜里终于调出来了，重构若干次最后是一个 9kb 屎山。
题意：
给出包含 Alternation（『候选』）、Concatenation（『连接』）、Kleene star（不清楚中文名称，后文成为『Kleene』）的正则表达式两个，输出一个长度最短的非空的可以匹配两个表达式的字符串，无解需报告。随机多测。
没有多测的弱化版：ICPC 防 AK 超级难题。可见本题应该评黑。
思路很明显，建立两个表达式的 DFA 然后想办法匹配。超级大模拟，难写难调。
Step 1
输入字符串，解释格式。讲讲我的处理方法：
更加标准的做法是先识别成语法树（这题的运算都是单目和双目，因此最终可以识别为一个二叉语法树），但是我直接边识别边建立自动机了。
一元运算符『Kleene』是左元运算符，烦人，先把串 reverse 一下，就变成了右元的单目运算符，一旦遇到，就先于后面的『表达式块』（后面有定义）进行结合。
考虑设计函数 pair<int, int> build(int l, int r) 为识别一段正则表达式的格式并建立 DFA，返回 DFA 的初始节点和汇总的接收态。
定义一个『表达式块』为：一个『括号』和里面的东西，一个『字符』，一个『Kleene』后接着一个表达式块。（下简称为『块』）
当前的状态是什么：空；单个块；若干『候选者』，每一个『候选者』是若干『块』。
空：直接新建一个节点，返回的自动机的初始节点和汇总的接收态都是这个节点。
单个块：如果是『括号』包起来的就直接 build 被括起来的串（当然代码实现的时候再父层可以直接调用括号内）；如果是『Kleene』开头的，build 后面的东西然套一个『Kleene』自动机壳（后文会提到）即可（当然代码中也可以直接让父层处理）。
若干『候选者』，每一个『候选者』是若干『块』：分离『块』和候选符，依次 build 每一个块，对于每一个候选的若干块，套上一个『Concatenation』自动机壳，最后套上一个『Alternation』自动机壳。
具体逻辑看代码，码风清晰易懂，带注释。
Step 2
设计自动机。
字符：直接建立两个节点只能用这一个字符转移即可。
操作符们（我愿意称之为壳）：下令 s 和 t 为旧自动机的初始态和终止态，S 和 T 为新自动机的初始态和终止态。没有化 s 和 t 中间的边因为不是操作符管的事。边均为 eps 类转移。
『Kleene』壳：
+-----+
v |
S---->s t---->T
| ^
+-----+『Alternation』壳（大于等于两个『候选者』同理）：
S---->s1 t1---->T
| ^
+---->s2 t2-----+
...『Concatenation』壳（大于等于两个被连接的自动机就继续连接就对了）：
s1 t1---->s2 t2...Step 3
DFA 的复合，具体逻辑是：对于旧的两个 DFA 上各选一个点的每一对点，在新的 DFA 上建立一个点对应这个状态，DFA 的 eps 类转移是专一一个原 DFA 的 eps 类转移，而非 eps 类转移是必须同时转移。
Step 4
在复合的自动机上找串。若一个非 eps 转移最后可以通过若干 eps 转移转移到接受态，那么这个转移可以被作为最后一个字符。最后看初始状态到最近的最后一个字符的最短路即可（非 eps 类的路径长度定义为
Step 5
写代码，准备好呕吐袋和棺材。
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
struct regular_expression {
int bracket_match[1005], bracket_stack[1005], begin, end, cnt;
vi eps_move[1005];
vector<int> mv[1005][128];
string s;
regular_expression(string &S) : s(S) {
memset(bracket_match, 0, sizeof(bracket_match));
bracket_stack[0] = 0;
for (int i = 0; i < s.size(); i++) { // 处理括号
if (s[i] == ')') {
s[i] = '(';
bracket_stack[++bracket_stack[0]] = i;
} else if (s[i] == '(') {
s[i] = ')';
bracket_match[bracket_stack[bracket_stack[0]--]] = i;
}
}
pii build_ans = build(0, s.size());
begin = build_ans.first;
end = build_ans.second;
}
void print() { // 调试用的输出
for (int i = 1; i <= cnt; i++) {
for (char c = 'a'; c <= 'z'; c++) {
for (int j : mv[i][c]) {
cout << i << " " << j << " " << c << endl;
}
}
for (int j : eps_move[i]) {
cout << i << " " << j << endl;
}
}
}
// 后面的是简单的辅助函数
int new_node() { // 建立新节点
return ++cnt;
}
int first_not_kleene(int x) { // 一段连续的 * 是与一个 * 等价的，直接找到后面的第一个非 * 就是这些 * 复制的『块』
while (s[x] == '*') {
x++;
}
return x;
}
int get_block_end(int x) { // 通过『块』首找『块』尾
if (s[x] == '(') {
return bracket_match[x] + 1; // 括号，提前预处理
}
return x + 1; // 字符，长度是 1 的『块』
}
// 后三个是题解中所谓的『套一个自动机壳』
pii kleene(int b, int e) { // 将自动机转为带『kleene』的自动机器
eps_move[e].push_back(b);
eps_move[b].push_back(e);
int new_b = new_node();
int new_e = new_node();
eps_move[new_b].push_back(b);
eps_move[e].push_back(new_e);
return {new_b, new_e};
}
pii concatenate(vpii &block) { // 将若干自动机前后拼接
if (block.empty()) {
int x = new_node();
return {x, x};
}
for (int i = 0; i + 1 < block.size(); i++) {
eps_move[block[i].second].push_back(block[i + 1].first);
}
return {block[0].first, block.back().second};
}
pii alternate(vpii &alternates) { // 将若干『候选』整合为一个自动机
if (alternates.empty()) {
int x = new_node();
int y = new_node();
return {x, y};
}
if (alternates.size() == 1) {
return alternates[0];
}
int x = new_node();
int y = new_node();
for (pii &i : alternates) {
eps_move[x].push_back(i.first);
eps_move[i.second].push_back(y);
}
return {x, y};
}
pii build(int l, int r) {
if (l == r) { // 『空』
int x = new_node();
return {x, x};
}
if (l + 1 == r) { // 『字符』
int x = new_node();
int y = new_node();
mv[x][s[l]].push_back(y);
return {x, y};
}
vector<vpii> block{{}};
while (l < r) {
if (s[l] == '|') { // 遇到『候选』标识符，新建一个『kleene』『块』组
block.push_back({});
l++;
} else if (s[l] == '*') { // 遇到『kleene』，找到这一段『kleene』控制的『块』并套一个『kleene』壳当做普通块
l = first_not_kleene(l);
pii block_ans = build(l, get_block_end(l));
block.back().push_back(kleene(block_ans.first, block_ans.second));
l = get_block_end(l);
} else if (s[l] == '(') { // 遇到『括号』，正常递归
block.back().push_back(build(l + 1, bracket_match[l]));
l = bracket_match[l] + 1;
} else { // 遇到『字符』，建立一个自动机
block.back().push_back(build(l, l + 1));
l++;
}
}
vpii alternates;
for (vpii &i : block) {
alternates.push_back(concatenate(i)); // 分别套上『链接』壳
}
return alternate(alternates); // 套上『候选』壳
}
} *pa1, *pa2;
bool vis[1005][1005]; // 访问过
bool all_eps[1005][1005]; // 有能力全 eps 到达终点
pair<pii, char> nxt[1005][1005]; // 下一个转移
int len[1005][1005]; // 非 0 min len
deque<pii> q;
vector<pair<pii, char> > e[1005][1005]; // 复合的自动机
void dfs(int pos1, int pos2) {
if (vis[pos1][pos2])
return;
vis[pos1][pos2] = 1;
if (pos1 == pa1->end && pos2 == pa2->end) {
all_eps[pos1][pos2] = 1;
return;
}
for (int i : pa1->eps_move[pos1]) {
dfs(i, pos2);
e[i][pos2].push_back({{pos1, pos2}, 'E'});
if (all_eps[i][pos2] && !all_eps[pos1][pos2])
all_eps[pos1][pos2] = 1;
}
for (int j : pa2->eps_move[pos2]) {
dfs(pos1, j);
e[pos1][j].push_back({{pos1, pos2}, 'E'});
if (all_eps[pos1][j] && !all_eps[pos1][pos2])
all_eps[pos1][pos2] = 1;
}
for (char c = 'a'; c <= 'z'; c++) {
for (int i : pa1->mv[pos1][c]) {
for (int j : pa2->mv[pos2][c]) {
dfs(i, j);
e[i][j].push_back({{pos1, pos2}, c});
if (all_eps[i][j]) { // 走一个有意义转移可以到达一个一直走无意义转移走到 {end, end}，那么这个转移走完之后可以直接作为结束字符
len[pos1][pos2] = 1;
nxt[pos1][pos2] = {{pa1->end, pa2->end}, c};
q.push_back({pos1, pos2});
}
}
}
}
}
void bfs() {
while (!q.empty()) {
pii t = q.front();
q.pop_front();
for (pair<pii, char> &i : e[t.first][t.second]) {
if (len[i.first.first][i.first.second] > len[t.first][t.second] + (i.second != 'E')) {
len[i.first.first][i.first.second] = len[t.first][t.second] + (i.second != 'E');
nxt[i.first.first][i.first.second] = {t, i.second};
if (i.second == 'E')
q.push_front(i.first);
else
q.push_back(i.first);
}
}
}
}
signed main() {
string str1, str2;
while (cin >> str1) {
cin >> str2;
reverse(all(str1));
reverse(all(str2));
regular_expression a1(str1), a2(str2);
pa1 = &a1;
pa2 = &a2;
for (int i = 0; i <= a1.cnt; i++) {
for (int j = 0; j <= a2.cnt; j++) {
vis[i][j] = all_eps[i][j] = 0;
len[i][j] = 100000;
e[i][j].clear();
}
}
q.clear();
dfs(a1.begin, a2.begin); // dfs 找出所有的末字符，同时建立复合自动机的反图
bfs(); // bfs 找出 {begin, begin} 到任意一个可以作为末字符的转移的最段路
if (len[a1.begin][a2.begin] > 10000) { // 无解，输出 Correct
cout << "Correct" << endl;
} else {
cout << "Wrong" << endl;
string ansans;
pii now = {a1.begin, a2.begin};
while (now != pii(a1.end, a2.end)) { // 根据搜索结果爬回串
ansans += nxt[now.first][now.second].second;
if (len[now.first][now.second] == 1 && nxt[now.first][now.second].second != 'E' && nxt[now.first][now.second].second != 'O' && nxt[now.first][now.second].second != 'F')
break;
now = {nxt[now.first][now.second].first.first, nxt[now.first][now.second].first.second};
}
reverse(ansans.begin(), ansans.end()); // 倒腾半天发现串是反的，reverse 一下就对了
for (char i : ansans)
if (i != 'E' && i != 'O' && i != 'F')
cout << i;
cout << endl;
}
}
return 0;
}