HDU 4271

字符串的编辑距离的扩展
[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);
    }
}

补充：软件开发 , C++ ,