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

如
输入：
ABCDEABCD
XAABZ
输出
3

#include <bits/stdc++.h>
#define int long long 
#define rep(i,a,n) for(int i =a;i<=n;i++)
#define per(i,a,n) for(int i =n;i>=a;i--)
#define fs first
#define sc second
using namespace std;

int dp[105][105];//s中前i个位置有j个和t相同的字符 
int a[105][105];

void solve(){
    string s,t;
    cin >> s >> t;
    int n,m;
    n=s.size();
    m=t.size();
    for(int i=1;i<=m;i++) dp[0][i]=1e9;
    for(int i=1;i<=n;i++) dp[i][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]);
        }
    }
    cout << dp[n][m];
}

signed main(){
   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}