文字列 \(S, T\) の最長共通部分列 (LCS) を求める方法として、次のような動的計画法がよく知られています。

\(\mathrm{dp}[i][j]\) を、\(S\) の先頭 \(i\) 文字と \(T\) の先頭 \(j\) 文字の LCS の長さと定義する。

\(\mathrm{dp}[i][j]\) の値が確定したら、次のように更新を行う。

• \(\mathrm{dp}[i + 1][j]\) を \(\max(\mathrm{dp}[i + 1][j], \mathrm{dp}[i][j])\) で更新する。
• \(\mathrm{dp}[i][j + 1]\) を \(\max(\mathrm{dp}[i][j + 1], \mathrm{dp}[i][j])\) で更新する。
• \(S\) の \(i+1\) 文字目と \(T\) の \(j + 1\) 文字目が等しいならば、 \(\mathrm{dp}[i + 1][j + 1]\) を \(\max(\mathrm{dp}[i + 1][j + 1], \mathrm{dp}[i][j] + 1)\) で更新する。

この動的計画法を応用して元の問題を解いてみましょう。元の問題では \(S\) を最大で \(K\) 回書き換えられるので、「\(S\) を何回書き換えたか」というのを動的計画法の状態として保持することを考えます。

\(\mathrm{dp}[i][j][k]\) を、\(S\) の先頭 \(i\) 文字を \(k\) 回書き換えたものと \(T\) の先頭 \(j\) 文字の LCS の長さと定義します。

\(\mathrm{dp}[i][j][k]\) の値が確定したら、まず、前述の動的計画法と同様の遷移を行います。

• \(\mathrm{dp}[i + 1][j][k]\) を \(\max(\mathrm{dp}[i + 1][j][k], \mathrm{dp}[i][j][k])\) で更新する。
• \(\mathrm{dp}[i][j + 1][k]\) を \(\max(\mathrm{dp}[i][j + 1][k], \mathrm{dp}[i][j][k])\) で更新する。
• \(S\) の \(i+1\) 文字目と \(T\) の \(j + 1\) 文字目が等しいならば、 \(\mathrm{dp}[i + 1][j + 1][k]\) を \(\max(\mathrm{dp}[i + 1][j + 1][k], \mathrm{dp}[i][j][k] + 1)\) で更新する。

さて、これだけでは \(S\) を書き換えるという操作が遷移に反映されていません。そこで、次の遷移を追加します。

• \(\mathrm{dp}[i + 1][j + 1][k + 1]\) を \(\max(\mathrm{dp}[i + 1][j + 1][k + 1], \mathrm{dp}[i][j][k] + 1)\) で更新する。

これら全ての遷移を実装すれば、値が正しく計算されます。状態数は \(O(|S||T|K)\) であるので、全体の計算量も \(O(|S||T|K)\) となります。

実装例 (C++) :

#include <bits/stdc++.h>
using namespace std;

void chmax(int& x, int y) {
    if (x < y) x = y;
}

int main() {
    string s, t;
    cin >> s >> t;
    int k;
    cin >> k;
    int n = s.size(), m = t.size();
    vector dp(n + 1, vector(m + 1, vector(k + 1, 0)));
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i != n) {
                for (int l = 0; l <= k; ++l) {
                    chmax(dp[i + 1][j][l], dp[i][j][l]);
                }
            }
            if (j != m) {
                for (int l = 0; l <= k; ++l) {
                    chmax(dp[i][j + 1][l], dp[i][j][l]);
                }
            }
            if (i != n and j != m) {
                if (s[i] == t[j]) {
                    for (int l = 0; l <= k; ++l) {
                        chmax(dp[i + 1][j + 1][l], dp[i][j][l] + 1);
                    }
                } else {
                    for (int l = 0; l < k; ++l) {
                        chmax(dp[i + 1][j + 1][l + 1], dp[i][j][l] + 1);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (const int x : dp[n][m]) {
        chmax(ans, x);
    }
    cout << ans << '\n';
}