Problem Statement

This problem fully contains Problem C (Operate 1), with $K \le 20$.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

Determine whether it is possible to perform the following operation on string $S$ between $0$ and $K$ times, inclusive, to make it identical to string $T$.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in $S$ (possibly the beginning or end).
  • Delete one character from $S$.
  • Choose one character in $S$ and replace it with another character.

Constraints

• Each of $S$ and $T$ is a string of length between $1$ and $500000$, inclusive, consisting of lowercase English letters.
• $K$ is an integer satisfying $\color{red}{1 \le K \le 20}$.

Input

The input is given from Standard Input in the following format:

K
S
T

Output

If $S$ can be made identical to $T$ with at most $K$ operations, print Yes; otherwise, print No.

Sample Input 1

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

• Replace the second character b with w. After the operation, the string becomes awc.
• Replace the third character c with f. After the operation, the string becomes awf.
• Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

算法1

(编辑距离暴力DP) $O(nm)$

$$ {dp_{i, j}}=\left\{ \begin{array}{l} dp_{i - 1, j - 1} && {a_i = b_j}\\ min(dp_{i - 1, j}, dp_{i, j - 1}, dp_{i - 1, j - 1}) && {a_i \neq b_i} \end{array} \right. $$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[2005][2005];
int main() {
    string a, b;
    int n, m, k;
    cin >> k >> a >> b;
    n = a.size(), m = b.size();
    a = ' ' + a, b = ' ' + b;
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) dp[0][i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            if (a[i] == b[j]) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            } 
        }
    }
    if (dp[n][m] <= k) cout << "Yes";
    else cout << "No";
    return 0;
}

算法2

(Ukkonen算法) $O(nk)$

Ukkonen算法可以求编辑距离在k以内的编辑距离

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int ukkonen_edit_distance(const string& s1, const string& s2, int k) {
    int m = s1.size();
    int n = s2.size();
    // 如果长度差超过 k，直接返回无穷大
    if (abs(m - n) > k) return INT_MAX;
    // 初始化 DP 表
    vector<vector<int>> dp(2, vector<int>(n + 1, INT_MAX));
    // 初始化第一行
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        // 初始化当前行的第一个元素
        dp[i % 2][0] = i;
        // 计算当前行的有效范围
        int start = max(1, i - k);
        int end = min(n, i + k);
        // 如果当前行的第一个元素不在有效范围内，设置为无穷大
        if (start > i) dp[i % 2][i - k] = INT_MAX;
        for (int j = start; j <= end; ++j) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            int del = (dp[(i - 1) % 2][j] == INT_MAX) ? INT_MAX : dp[(i - 1) % 2][j] + 1;
            int ins = (dp[i % 2][j - 1] == INT_MAX) ? INT_MAX : dp[i % 2][j - 1] + 1;
            int rep = (dp[(i - 1) % 2][j - 1] == INT_MAX) ? INT_MAX : dp[(i - 1) % 2][j - 1] + cost;
            dp[i % 2][j] = min({del, ins, rep});
            // 如果当前编辑距离超过 k，提前终止
            if (dp[i % 2][j] > k) dp[i % 2][j] = INT_MAX;
        }
        // 如果当前行的最后一个元素不在有效范围内，设置为无穷大
        if (end < n) dp[i % 2][end + 1] = INT_MAX;
    }
    // 返回编辑距离
    return (dp[m % 2][n] <= k) ? dp[m % 2][n] : INT_MAX;
}

int main() {
    int k;
    string s1, s2;
    cin >> k;
    cin >> s1 >> s2;
    int distance = ukkonen_edit_distance(s1, s2, k);
    if (distance != INT_MAX) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}