Codeforces Round #201 (Div. 1) B. Lucky Common Subsequence

昔流行ってたのかな…最近よく見る文字列の状態遷移問題。

問題

codeforces.com

解法

上で書いたように, まず virus の状態遷移をはっきりさせます。蟻本の 4 章に書いてある文字列テクニックを使います。

で, そしたら

dp[x1][x2][x3] = (s1 の x1 文字目まで, s2 の x2 文字目まで見た時, virus の x3 文字目まで subsequence が一致している時の, 最大共通文字数)

という dp を求めます。この dp には同時に, 「最大共通文字数になる時の直前の状態」 もメモして入れておきます。
そうすることで, 復元がやりやすくなります。

const int MAXN = 103;
struct state {
    int score;
    int b1, b2, b3;
    bool operator<(const state& rhs) const {return score < rhs.score;}
};
state dp[MAXN][MAXN][MAXN];
int nState[MAXN][26];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s1, s2, virus;
    cin >> s1;
    cin >> s2;
    cin >> virus;
    int n1 = s1.size(), n2 = s2.size(), n3 = virus.size();
    // state
    for (int i = 0; i < n3; i++) {
        string s = virus.substr(0, i);
        for (int j = 0; j < 26; j++) {
            char c = (char)('A'+j);
            string ns = s;
            ns += c;
            while (virus.substr(0, ns.size()) != ns) ns = ns.substr(1);
            nState[i][j] = ns.size();
        }
    }
    // dp
    for (int i = 0; i <= n1; i++) for (int j = 0; j <= n2; j++) {
        for (int k = 0; k <= n3; k++) dp[i][j][k].score = -MAXN;
    }
    dp[0][0][0] = state{0, -1, -1, 0};
    for (int x1 = 0; x1 <= n1; x1++) for (int x2 = 0; x2 <= n2; x2++) {
        for (int v = 0; v < n3; v++) {
            if (dp[x1][x2][v].score < 0) continue;
            //cout << x1 << "  " << x2 << "  " << v << "  " << dp[x1][x2][v].score << endl;
            dp[x1+1][x2][v] = max(dp[x1+1][x2][v], dp[x1][x2][v]);
            dp[x1][x2+1][v] = max(dp[x1][x2+1][v], dp[x1][x2][v]);
            if (x1 < n1 && x2 < n2 && s1[x1] == s2[x2]) {
                state p = state{dp[x1][x2][v].score + 1, x1, x2, v};
                int nv = nState[v][s1[x1]-'A'];
                dp[x1+1][x2+1][nv] = max(dp[x1+1][x2+1][nv], p);
            }
        }
    }
    int maxi = 0;
    int x3 = 0;
    for (int i = 0; i < n3; i++) {
        //cout << dp[n1][n2][i].score << endl;
        if (maxi < dp[n1][n2][i].score) {
            maxi = dp[n1][n2][i].score;
            x3 = i;
        }
    }
    if (maxi == 0) {
        cout << 0 << endl;
        return 0;
    }
    string ans;
    int x1 = n1, x2 = n2;
    while (1) {
        int t1 = x1, t2 = x2, t3 = x3;
        x1 = dp[t1][t2][t3].b1;
        x2 = dp[t1][t2][t3].b2;
        x3 = dp[t1][t2][t3].b3;
        if (x1 < 0) break;
        ans += s1[x1];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}