思路：考的是字符串的编辑距离。在蓝桥杯2012年决赛上出现过。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[][];
char targ[],ans;
int Min(int a,int b,int c)
{
int temp;
temp=a<b?a:b;
return temp<c?temp:c;
}
int getMin(char *str1,char *str2)
{
int l1,l2,i,j;
l1=strlen(str1);
l2=strlen(str2);
for(i=;i<=l2;i++)
dp[][i]=i;
int ans=l2;
for(i=;i<l1;i++)
{
for(j=;j<l2;j++)
{
if(str1[i]==str2[j])
dp[i+][j+]=Min(dp[i][j],dp[i][j+]+,dp[i+][j]+);
else
dp[i+][j+]=Min(dp[i][j+],dp[i+][j],dp[i][j])+;
}
ans=min(ans,dp[i+][l2]);
}
return ans;
}
void solve(char *str1,char *str2)
{
int i,j,l1,l2,t;
l1=strlen(str1);
l2=strlen(str2);
if(l2*<l1)
{
for(i=;i<l1;i++)
str1[i+l1]=str1[i];
str1[i+l1]='\0';
t=getMin(str1,str2);
if(t<=ans)
{
if(t==ans)
{
if(strcmp(targ,str2)>)
strcpy(targ,str2);
}
else
{
strcpy(targ,str2);
ans=t;
}
}
str1[l1]='\0';
}
else
{
char str3[];
for(i=;i<l1;i++)
{
for(j=;j<l1;j++)
{
str3[j]=str1[(i+j)%l1];
}
str3[j]='\0';
t=getMin(str3,str2);
if(t<=ans)
{
if(t==ans)
{
if(strcmp(targ,str2)>)
strcpy(targ,str2);
}
else
{
strcpy(targ,str2);
ans=t;
}
}
}
}
}
int main()
{
char str1[],str2[];
int i,j,n;
while(scanf("%s",&str1)!=EOF)
{
memset(dp,,sizeof(dp));
scanf("%d",&n);
ans=;
int t;
for(i=;i<=n;i++)
{
scanf("%s",str2);
solve(str1,str2);
}
printf("%s %d\n",targ,ans);
}
return ;
}