题目描述

只是把上一个编辑距离和这个结合了一下
需要注意的就是 刚开始没法ac 后来注释掉了memset

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char tpl[1001][12];
char x[12];
int num;
int f[1002][1002];
int cal(char a[],char b[])
{
    int m=strlen(a),n=strlen(b);
    //memset(f,0,sizeof(f));
    for(int j=0;j<=n;j++) f[0][j]=j;
    for(int j=0;j<=m;j++) f[j][0]=j;

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1];
            else f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+1);
        }
    }
    return f[m][n];

}
int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    for(int i=0;i<m;i++)
    {
        scanf("%s",tpl[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%s %d",x,&num);
        int res=0;
        for(int j=0;j<m;j++)
        {
            //cout<<tpl[i]<<" "<<x<<" "<<cal(tpl[i],x)<<endl;
            if(cal(tpl[j],x)<=num) 
            {
                res++;
            }
        }
        printf("%d\n",res);

    }
    return 0;
}