Problem Statement

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.

Solving

我们定义 $dp[i][j] = $ {由 $S$ 的前 $i$ 个字符组成的字符串与由 $T$ 的前 $j$ 个字符组成的字符串之间的编辑距离}

从 $dp[0][0]=0$ 和 $dp[i][j]= \infty$ 开始处理其他 $(i,j)$ ，我们使用升序双循环来处理如下转换：

• $dp[i][j]=\min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+C)$
• $C=0 ,\ $ ${\rm if}$ $S_i=T_j$
• $C=1 ,\ $ ${\rm otherwise}.$

注:此题不存在i或j等于0的情况，完整的状态转移方程应包括:

$dp[i][j]=j $            ${\rm i = 0}.$

$dp[i][j]=i $             ${\rm j = 0}.$

通过上述 DP，可以得到所需的 DP 表。

以 horse 和 coser 两个字符串为例:

然而，由于时间限制，我们无法在规定的执行时间内完成。

尽管如此，我们仍可以通过调整这个解决方案来解决这个问题。

在这个问题中，我们要问的是是否 $d(S,T) \le K$ ，而我们的约束条件是 $K \le 20$ 。
例如，考虑 $dp[10][50]$ 。这是 $S$ 的前 $10$ 个字符组成的字符串与 $T$ 的前 $50$ 个字符组成的字符串之间的编辑距离，但由于我们需要匹配它们的长度，因此距离至少为 $40$ （无论内容如何）。
任何 DP 变换都不会使数值变小，因此检查像 $dp[10][50]$ 这样明显超过 $K$ 的内容是没有用的，因为我们已经限制了 $K \le 20$ ，只需确定是否有 $d(S,T) \le K$ 。

因此，我们只需从 $dp[i][i-K]$ 到 $dp[i][i+K]$ 进行求值，并将 $dp[i][j] = \infty$ 置于 $dp[i][j] = \infty$ 之外，就能确定 $d(S,T) \le K$ 是否存在。
因此，只需正确填写 DP 表的一部分，就可以在总共 $O(|S|K)$ 的时间内解决这个问题。在执行过程中，请注意 $S$ 和 $T$ 的长度相差 $K$ 或更多的情况。

以下是使用C++语言编写的程序代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<bits/stdc++.h>
using namespace std;
int main(){
  int k;
  string s,t;
  cin >> k >> s >> t;
  int sl=s.size();
  int tl=t.size();
  //if the difference between the length of s and t is greater than k, then it is impossible to convert s to t
  if(abs(sl-tl)>k){
    cout << "No\n";
    return 0;
  }
  //dp[sl+1][2*k+1] = {1e9};
  vector<vector<int>> dp(sl+1,vector<int>(2*k+1,1e9));
  dp[0][k]=0;
  for(int i=0;i<=sl;i++)
  {
    for(int dj=0;dj<=2*k;dj++)
    {
      int j=i+dj-k;//j is the length of the prefix of t
      if(j<0) continue;
      if(j>tl) break;
    //insert operation
      if(i>0 && dj<2*k)
      {
        dp[i][dj]=min(dp[i][dj],dp[i-1][dj+1]+1);
      }
    //delete operation
      if(j>0 && dj>0)
      {
        dp[i][dj]=min(dp[i][dj],dp[i][dj-1]+1);
      }
    //replace operation
      if(i>0 && j>0)
      {
        int add=1;
        if(s[i-1]==t[j-1]){ add=0; }
        dp[i][dj]=min(dp[i][dj],dp[i-1][dj]+add);
      }
    }
  }
  if(dp[sl][k+tl-sl]<=k){cout << "Yes\n";}
  else{cout << "No\n";}
  return 0;
}