算法介绍

利用902.最短编辑距离的dp算法link，一次次求出给定的所有目标字符串是否符合当前的目标串的操作次数要求

优化

1.memset()

memset()函数真的很耗时间，去掉memset()之前一直超时，去掉之后就ac了(4775ms)

2.min()不要用三个及以上参数的重载

min({a,b,c})的时候4775ms
a=min(a,b),min(a,c)化解成两个两参数形式，时间降为2046ms

3.string

使用char数组而不是string类
char-》2046ms string-》3132ms

代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int N=1010;
const int MAX=20;
int f[N][N];//f[i][j]表示x串前i个字符变成tar串前j个字符，在x前i个字符的基础上需要进行的最少操作次数
bool ifplus(char x[],char tar[],int cns,int n1,int m1){
   // memset(f,0,sizeof(f));
    for(int i=0;i<=n1;i++) f[i][0]=i; //删
    for(int i=0;i<=m1;i++) f[0][i]=i;//增
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=m1;j++){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            f[i][j]=min(f[i][j],f[i-1][j-1]+(x[i]!=tar[j]));
        }
    }
    if(f[n1][m1]<=cns) return true;
    return false;
}
int main(void){
    int n,m,i=0,k=0;
    cin>>n>>m;
    char v[n+1][MAX];
    while(i++<n){
        cin>>(v[i]+1);
        v[i][0]=1;
    }
    while(k++<m){
        char tar[MAX];
        cin>>tar+1;
        tar[0]=1;
        int m1=strlen(tar)-1;
        int cns;
        cin>>cns;
        int ans=0,n1;
        for(int i=1;i<=n;i++){
            n1=strlen(v[i])-1;
            if(ifplus(v[i],tar,cns,n1,m1)) ans++;
        }
        cout<<ans<<endl;
    }
}