利用最短编辑距离的思路及代码,对输入输出稍作处理即可:
几个细节:
细节1:输入字符串时,从字符数组的下标1开始输入。
解释:因为状态转移方程涉及i-1,所以把下标从1开始
细节2:
edit_distance中,求字符数组长度是:
strlen(a+1)
a是从下标1开始读取,下标为0处一直是0,strlen读取字符数组长度的标准是读到0为止,如果从a开始的话,他一开始读取的a[0]就是0,所以返回的长度只会是0
细节3:
char str[M][N];
for(int i=0;i<n;i++)
cin>>str[i]+1;
解释这个输入方式:每一个字符串的每一个字符在这个字符串里面的位置加一,第二维限定了每个字符串的长度
str[i]是从i=1开始读取的,i=0没有读取任何字符。
细节4:
cin>>s+1>>limit;
int cnt=0;//存储该字符串符合limit次数的有多少
for(int i=0;i<n;i++)
if(edit_distance(str[i],s)<=limit) cnt++;
之所以从0开始遍历,是因为所有字符串在第一维是从0开始存储的,但在第二维是从1开始存储的。
c++:
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=15,M=1010;
char str[M][N];//存储读入的所有字符串
int f[N][N];
int n,m;
int edit_distance(char a[],char b[]){
int la=strlen(a+1);//从a+1开始计算长度,因为main中的字符数组都是从1开始存储的
int lb=strlen(b+1);//因为a是从下标1开始读取,下标为0处一直是0,strlen读取字符数组长度的标准是读到0为止,如果从a开始的话,他一开始读取的a[0]就是0,所以返回的长度只会是0
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-1][j],f[i][j-1])+1;
if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
return f[la][lb];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>str[i]+1;
while(m--){
char s[N];//每行的字符串
int limit;//每行的限制
cin>>s+1>>limit;
int cnt=0;//存储该字符串符合limit次数的有多少
for(int i=0;i<n;i++)//这里的str[i]+1的意思是,每一个字符串的每一个字符在这个字符串里面的位置加一,从零开始读是将每一个字符串从零开始存在字符串数组中的位置,两者并不冲突
if(edit_distance(str[i],s)<=limit) cnt++;
cout<<cnt<<endl;
}
return 0;
}