Edit distance (linear dp+ violence matching)

Topic link

https://www.acwing.com/problem/content/901/

Ideas

In fact, the idea of this question is the same as that of the previous question , It's just that we need to do something about every inquiry n Secondary matching judgment , If the current number of operations is less than k That means our string is legal , The minimum number of times it takes to match two strings , We can do the last one ： Minimum edit distance

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+10;

int n,m;
char a[N][15],b[20];
int f[20][20],la[N];


int main()
{
    
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) {
    
		cin>>(a[i]+1);
		la[i]=strlen(a[i]+1);
	}
	while(m--){
    
		int cnt;
		cin>>(b+1)>>cnt;
		int lb = strlen(b+1);
		int ans = 0;
		for(int i = 1;i <= n; ++i) {
    
			// initialization 
			for(int j = 0;j <= la[i]; ++j) f[j][0] = j;
			for(int j = 0;j <= lb; ++j) f[0][j] = j;

			for(int j = 1;j <= la[i]; ++j)
				for(int k = 1;k <= lb; ++k){
    
				f[j][k] = min(f[j-1][k]+1,f[j][k-1]+1);
				if(a[i][j] == b[k]) f[j][k] = min(f[j-1][k-1],f[j][k]);
				else f[j][k] = min(f[j-1][k-1] + 1,f[j][k]);
			}
			if(f[la[i]][lb] <= cnt) ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}