题目描述

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

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

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

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

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

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

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

样例

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

算法

(线性DP) $O(n^2)$

状态函数：f[i][j]表示使A的前i个字符包含B的前j个字符最少需要修改多少次
状态转移方程：if（a[i][j] == b[i][j]) f[i][j] = f[i-1][j-1];
else f[i][j] = min(f[i-1][j], f[i-1][j-1]+1);
与模板题最长公共子序列 类似，以最后一个字符i,j为划分依据，如果相等则修改次数等于f[i-1][j-1]，如果不相等，则取min(f[i-1][j], f[i-1][j-1]+1)

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int f[N][N];

int main()
{
    string t, s;
    cin >> t >> s;

    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for(int i = 1; i <= t.size(); i++)
    {
        f[i][0] = 0;
        for(int j = 1; j <= s.size(); j++)
        {
            if(t[i-1] == s[j-1]) f[i][j] = f[i-1][j-1];
            else f[i][j] = min(f[i-1][j], f[i-1][j-1] + 1);
        }
    }

    cout << f[t.size()][s.size()] << endl;
    return 0;
}