[数据结构与算法]【acwing】899. 编辑距离**(线性dp）

穿越隧道

最短编辑距离的微变型
需要仔细阅读题目。

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

using namespace std;

const int N = 1e3 + 10, M = 20;

int n,m;
char g[N][M];
int f[M][M];
int edit_distance(char a[], char b[]){//最短编辑距离部分
	int la = strlen(a + 1);
	int lb = strlen(b + 1);
	for(int i = 0; i <= la; i++) f[i][0] = i;
	for(int j = 0; j <= lb; j++) f[0][j] = j;
	for(int i = 1; i <= la; i++){
		for(int j = 1; j <= lb; j++){
			f[i][j] = min(f[i-1][j] + 1, f[i][j - 1] + 1);
			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);
		}
	}
	return f[la][lb];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++) scanf("%s",g[i] + 1);
	while(m--){
		char s[M];
		int limit;
		scanf("%s%d",s + 1, &limit);
		int res = 0;
		for(int i = 0; i < n; i++)
			if(edit_distance(g[i],s) <= limit){
				res++;
			}
		printf("%d\n",res);
	}
	return 0;
}