题目描述

899.编辑距离
这道题和902题算法是一样的，都是同一类问题 只不过这道题是有多组测试数据 它其实就是902题的序列a 然后又有多组比较的数据b 还有对应的最大操作数 问我们a中有多少个数据序列满足能变成b 而且操作数小于b 不过是我们在开始前我们要将输入一个二维数组a 不断的输入多组的测试数据 在到了每组的测试数据中判断序列的一项相等的方法是a[i][j]=b[k] 最后比较如果f[len1][len2]<=maxlen 就答案加一res++ 最后输出这个res就是一组数据的成功输出 知道while(m–)的循环阶数 m表示测试数据的数量包括m行 每行有个序列b 和maxlen操作数

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m;
const int N =1010;
const int M =15;
int f[N][N];
char a[N][M]; 
int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)    cin>>a[i];
    while(m--)
    {
        int maxlen;
        int res =0;
        string b;
        cin>>b>>maxlen;
        int len2=b.size();      
        for(int i=1;i<=n;i++)
        {
            memset(f,0,sizeof f);
            int len1=strlen(a[i-1]);
            for(int j=1;j<=len1;j++)
                for(int k=1;k<=len2;k++)
                {
                    f[j][0]=j;
                    f[0][k]=k; 
                }
            for(int j=1;j<=len1;j++)
                for(int k=1;k<=len2;k++)
                {
                    f[j][k]=min(f[j-1][k]+1,f[j][k-1]+1);
                    if(b[k-1]==a[i-1][j-1]) f[j][k]=min(f[j][k],f[j-1][k-1]);
                    else    f[j][k]=min(f[j][k],f[j-1][k-1]+1);
                }
            if(f[len1][len2]<=maxlen)   res++;


        }
        cout<<res<<endl;


    }

    return 0;
}