题目描述

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T？

输入格式
输入两行，每行一个字符串。

第一行的字符串为 S，第二行的字符串为 T。

两个字符串均非空而且只包含大写英文字母。

输出格式
输出一个整数，表示答案。

数据范围
1≤|T|≤|S|≤1000

样例

输入样例：
ABCDEABCD
XAABZ
输出样例：
3

算法1

(DP) $O(nm)$

一共分为4种情况
f[i-1][j-1],f[i][j-1],f[i-1][j],f[i][j];

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
char a[1100],b[1100];
int f[1100][1100];
int main()
{
    scanf("%s %s",a+1,b+1);
    memset(f, 0x3f, sizeof f);
    f[0][0]=0;
    int n=strlen(a+1),m=strlen(b+1);
    for(int i=1;i<=n;i++)
    {
        f[i][0]=0;
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i] == b[j])  f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else  f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    printf("%d",f[n][m]);
    return 0;
}