字符串编辑距离模板

编辑距离，⼜又称Levenshtein距离（也叫做Edit Distance），是指两个字串串之间，由⼀一个转成 另⼀一个所需的少编辑操作次数。许可的编辑操作包括将⼀一个字符替换成另⼀一个字符，插⼊入⼀一个字 符，删除⼀一个字符

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5; 
int T, cas = 0; 
int n, m; 
int dp[N][N]; 
char s[N], t[N]; 
int main(){
	while(scanf("%s%s",s,t)!=EOF){
		int n=(int)strlen(s),m=(int)strlen(t);
		for(int i=0;i<=n;i++){
			dp[i][0]=i;
		}
		for(int i=0;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])+1;
				dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(s[i-1]!=t[j-1]));
			}
		}
		printf("%d\n",dp[n][m]);
	}
}