hdu 1516 String Distance and Transform Process(編集距離+変更経路保存)
1852 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1516
それとも距離を編集しますか?ここでは編集プロセスを同時に出力します.最初は編集プロセスを出力するしかないと思いましたが、dfsは長い間続いています.それぞれ2つの文字列にdp[i][j]の変化によって逆押しすればいいです.
それとも距離を編集しますか?ここでは編集プロセスを同時に出力します.最初は編集プロセスを出力するしかないと思いましたが、dfsは長い間続いています.それぞれ2つの文字列にdp[i][j]の変化によって逆押しすればいいです.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s1[100],s2[100];
int dp[100][100];
int step;
int len1,len2;
void solve()
{
memset(dp,0,sizeof(dp));
for(int i = 0; i <= len1; i++)
dp[i][0] = i;
for(int i = 0; i <= len2; i++)
dp[0][i] = i;
for(int i = 1; i <= len1; i++)
{
for(int j = 1; j <= len2; j++)
{
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]+1);
}
}
}
void path()
{
int tmp;
int i,j;
for(i = len1,j = len2;;)
{
if(i < 1 && j < 1)
break;
if(s1[i-1] == s2[j-1])
tmp = 0;
else tmp = 1;
if(dp[i][j] == dp[i-1][j-1]+tmp && i >= 1 && j >= 1)
{
if(tmp) // ,i--,j--;
printf("%d Replace %d,%c
",++step,i,s2[j-1]);
i--;
j--;
}
else if(dp[i][j] == dp[i-1][j]+1 && i >= 1)// i,i--
{
printf("%d Delete %d
",++step,i);
i--;
}
else if(dp[i][j] == dp[i][j-1]+1 && j >= 1)// i+1 ,j--
{
printf("%d Insert %d,%c
",++step,i+1,s2[j-1]);
j--;
}
}
}
int main()
{
while(~scanf("%s %s",s1,s2))
{
len1 = strlen(s1);
len2 = strlen(s2);
solve();
printf("%d
",dp[len1][len2]);
step = 0;
path();
}
return 0;
}