题目特征描述
(1)给定若干个字符串(字符串长度较小);
(2)输入一个新的字符串,在给定字符串中查询有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串;
解题思路
(1)本题属于最短编辑距离的延伸应用题,即将最短编辑距离作为一个函数来调用;
(2)最短编辑距离 ≤ 上限操作次数时,即字符串满足条件;
细节:char a[n]
①字符串在读取时,要后移一个地址,即cin>>a+1;
②<cstring>或<string.h>的头文件中,通过调用strlen(),读取字符数组长度,即la = strlen(a);
算法1
时间复杂度 $O(n^3)$
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 15,M=1010;
int n,m;
int f[N][N];
char str[M][N];
int editdist(char a[],char b[])
{
int la = strlen(a+1), lb = strlen(b+1);
for(int i = 0;i<=lb;i++) f[0][i] = i;
for(int i = 0;i<=la;i++) f[i][0] = i;
for(int i = 1;i<=la;i++)
for(int j = 1;j<=lb;j++)
{
f[i][j] = min(f[i][j-1]+1,f[i-1][j]+1);
f[i][j] = min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
}
return f[la][lb];
}
int main()
{
//input
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>str[i]+1;
//processing
while(m--)
{
char a[N];
int limit,cnt = 0;
cin>>a+1>>limit;
for (int i = 1; i <= n ; i++)
{
if(editdist(str[i],a)<=limit) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}