字符串的編輯距離的擴展
[cpp]
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
char s[100100],tmp[100100],str[20][20],temp[100100];
int dp[100100][20];
int n,l1,l2;
int pos,ans;
int cal(char * s1,char * s2,int len1,int len2){ //這裡dp[i][j]表示s2的0~j的字串成為s1的0～i的字串最小距離
int i,j;
//memset(dp,0,sizeof(dp)); //被MEMSET卡了！！！！！！
//for(int i=0;i<=l1;i++) 如果這四行加上，dp[i][j]表示的是s1串前i位與s2前j位的全部匹配的編輯距離
//{
// dp[i][0] = i;
//}
for(i=0;i<=len2;i++)
dp[0][i]=i;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++){
dp[i][j]=min(min(dp[i][j-1],dp[i-1][j])+1,dp[i-1][j-1]+(s1[i-1]!=s2[j-1]));
}
int tem=20;
for(i=1;i<=len1;i++)
tem=min(tem,dp[i][len2]);
return tem;
}
int main(){
int i,j,k;
while(scanf("%s",s)!=EOF){
l1=strlen(s);
strcpy(tmp,s);
for(j=0;j<10 && j<l1;j++)
tmp[l1+j]=s[j];
tmp[l1+j]='\0';
scanf("%d",&n);
ans=20;
for(i=1;i<=n;i++){
scanf("%s",str[i]);
l2=strlen(str[i]);
if(l1>=l2*2){
int tem=cal(tmp,str[i],l1+l2,l2);
if(tem<ans){
ans=tem;
pos=i;
}
else if(tem==ans){
if(strcmp(str[i],str[pos])<0)
pos=i;
}
}
else{
for(j=0;j<l1;j++){
for(k=0;k<l1;k++)
temp[k]=s[(j+k)%l1];
temp[k]='\0';
int tem=cal(temp,str[i],l1,l2);
if(tem<ans){
ans=tem;
pos=i;
}
else if(tem==ans){
if(strcmp(str[i],str[pos])<0)
pos=i;
}
}
}
}
printf("%s %d\n",str[pos],ans);
}
}
