gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define iter(v) __typeof((v).begin())
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair <int,int> PII;
typedef PII AM;
ll sqr(ll x) {return x * x;}
template <class T> void checkmax(T &t, T x){if (x > t) t = x;}
template <class T> void checkmin(T &t, T x){if (x < t) t = x;}
template <class T> void _checkmax(T &t, T x){if (t == -1 || x > t) t = x;}
template <class T> void _checkmin(T &t, T x){if (t == -1 || x < t) t = x;}

const int N = 1005;
int poolCnt;
vector <PII> E[N];
stack <PII> num;
stack <int> op;
bool vis[N][N][2];
int d[N][N][2];
pair <int,PII> fa[N][N][2];
int chr[N][N][2];
int pos;
char s[N];

AM operator + (AM a, AM b) {
    E[a.second].push_back(PII(-1, b.first));
    return AM(a.first, b.second);
}

AM operator * (AM a) {
    E[poolCnt].push_back(PII(-1, a.first));
    E[a.second].push_back(PII(-1, poolCnt + 1));
    E[poolCnt].push_back(PII(-1, poolCnt + 1));
    E[poolCnt + 1].push_back(PII(-1, poolCnt));
    poolCnt += 2;
    return AM(poolCnt - 2, poolCnt - 1);
}

AM operator | (AM a, AM b) {
    E[poolCnt].push_back(PII(-1, a.first));
    E[poolCnt].push_back(PII(-1, b.first));
    poolCnt++;
    E[a.second].push_back(PII(-1, poolCnt));
    E[b.second].push_back(PII(-1, poolCnt));
    poolCnt++;
    return AM(poolCnt - 2, poolCnt - 1);
}

AM newAM(int c) {
    E[poolCnt].push_back(PII(c, poolCnt + 1));
    poolCnt += 2;
    return AM(poolCnt - 2, poolCnt - 1);
}

AM Expr();

AM Item() {
    AM res;
    if (s[pos] == '(') {
        pos++;
        res = Expr();
        pos++;
    } else {
        res = newAM(s[pos] - 'a');
        pos++;
    }
    while (s[pos] == '*') {
        res = *res;
        pos++;
    }
    return res;
}

AM Concat() {
    AM res = Item();
    while (s[pos] && s[pos] != ')' && s[pos] != '|') {
        res = res + Item();
    }
    return res;
}

AM Expr() {
    AM res = Concat();
    while (s[pos] && s[pos] != ')') {
        pos++;
        res = res | Concat();
    }
    return res;
}

#define MT(x, y, z) make_pair(x, make_pair(y, z))
#define X first
#define Y second.first
#define Z second.second

queue < pair <int, PII> > Q;

void push(int w, int x, int y, int fx, int fy, int ftype, int c) {
    if (d[x][y][0] == -1 || w < d[x][y][0]) {
        d[x][y][0] = w;
        fa[x][y][0] = make_pair(ftype, make_pair(fx, fy));
        chr[x][y][0] = c;
        if (!vis[x][y][0]) {
            vis[x][y][0] = 1;
            Q.push(make_pair(0, make_pair(x, y)));
        }
    }
    if (w && (d[x][y][1] == -1 || w < d[x][y][1])) {
        d[x][y][1] = w;
        fa[x][y][1] = make_pair(ftype, make_pair(fx, fy));
        chr[x][y][1] = c;
        if (!vis[x][y][1]) {
            vis[x][y][1] = 1;
            Q.push(make_pair(1, make_pair(x, y)));
        }
    }
}

void gao(PII at1, PII at2) {
    while (!Q.empty()) Q.pop();
    rep(i, poolCnt) sort(E[i].begin(), E[i].end());
    memset(vis, 0, sizeof(vis));
    memset(d, 0xff, sizeof(d));
    Q.push(MT(0, at1.first, at2.first));
    d[at1.first][at2.first][0] = 0;
    vis[at1.first][at2.first][0] = 1;
    while (!Q.empty()) {
        int type = Q.front().X;
        int x = Q.front().Y;
        int y = Q.front().Z;
        Q.pop();
        int w = d[x][y][type];
        vis[x][y][type] = 0;
        int i = 0, j = 0;
        while (i < (int)E[x].size() && E[x][i].first == -1) {
            push(w, E[x][i++].second, y, x, y, type, -1);
        }
        while (j < (int)E[y].size() && E[y][j].first == -1) {
            push(w, x, E[y][j++].second, x, y, type, -1);
        }
        if (i != (int)E[x].size() && j != (int)E[y].size() && E[x][i].first == E[y][j].first) {
            push(w + 1, E[x][i].second, E[y][j].second, x, y, type, E[x][i].first);
        }
    }
    if (d[at1.second][at2.second][1] == -1) {
        puts("Correct");
    } else {
        puts("Wrong");
        string s;
        int x = at1.second;
        int y = at2.second;
        int type = 1;
        while (!(x == at1.first && y == at2.first && !type)) {
            if (chr[x][y][type] != -1) s = (char)(chr[x][y][type] + 'a') + s;
            pair <int,PII> o = fa[x][y][type];
            x = o.second.first;
            y = o.second.second;
            type = o.first;
        }
        printf("%s\n", s.c_str());
    }
}

int main() {
    freopen("disjoint.in", "r", stdin);
    freopen("disjoint.out", "w", stdout);
    poolCnt = 0;
	scanf("%s", s);
	pos = 0;
	PII automaton1 = Expr();
	scanf("%s", s);
	pos = 0;
	PII automaton2 = Expr();
	gao(automaton1, automaton2);
	return 0;
}