HDu 4271動的計画
8382 ワード
考え方:文字列の編集距離を試験します.ブルーブリッジカップ2012年決勝に出場したことがある.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[200050][20];
char targ[20],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=1;i<=l2;i++)
dp[0][i]=i;
int ans=l2;
for(i=0;i<l1;i++)
{
for(j=0;j<l2;j++)
{
if(str1[i]==str2[j])
dp[i+1][j+1]=Min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1);
else
dp[i+1][j+1]=Min(dp[i][j+1],dp[i+1][j],dp[i][j])+1;
}
ans=min(ans,dp[i+1][l2]);
}
return ans;
}
void solve(char *str1,char *str2)
{
int i,j,l1,l2,t;
l1=strlen(str1);
l2=strlen(str2);
if(l2*2<l1)
{
for(i=0;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)>0)
strcpy(targ,str2);
}
else
{
strcpy(targ,str2);
ans=t;
}
}
str1[l1]='\0';
}
else
{
char str3[20];
for(i=0;i<l1;i++)
{
for(j=0;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)>0)
strcpy(targ,str2);
}
else
{
strcpy(targ,str2);
ans=t;
}
}
}
}
}
int main()
{
char str1[200050],str2[20];
int i,j,n;
while(scanf("%s",&str1)!=EOF)
{
memset(dp,0,sizeof(dp));
scanf("%d",&n);
ans=100;
int t;
for(i=1;i<=n;i++)
{
scanf("%s",str2);
solve(str1,str2);
}
printf("%s %d
",targ,ans);
}
return 0;
}