fork(4) download
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define si 3005
  4. #define min(a,b) (a<b?a:b)
  5. int dp[si][si],l1,l2,dir[si][si];
  6. char ch1[si],ch2[si];
  7.  
  8. int rec(int i,int j)
  9. {
  10. if(i<0&&j<0)
  11. return 0;
  12. else if(i<0||j<0)
  13. return i<0?(j+1):(i+1);
  14. int &ret=dp[i][j];
  15. if(ret!=-1)
  16. return ret;
  17. int p1=rec(i,j-1)+1; //del
  18. int p2=rec(i-1,j)+1; //add
  19. int p3;
  20. if(ch1[i]==ch2[j])
  21. p3=rec(i-1,j-1);
  22. else
  23. p3=rec(i-1,j-1)+1;
  24. if(p1<=p2&&p1<=p3)
  25. dir[i][j]=1;
  26. else if(p2<=p1&&p2<=p3)
  27. dir[i][j]=2;
  28. else
  29. dir[i][j]=3;
  30. ret=min(p1,min(p2,p3));
  31. return ret;
  32. // return ret=min(p1,min(p2,p3));
  33. }
  34.  
  35. void path_prnt(int i,int j)
  36. {
  37. if(i<0||j<0)
  38. return;
  39. if(dir[i][j]==1)
  40. {
  41. path_prnt(i,j-1);
  42. printf("delete %c",ch1[i]);
  43. }
  44. else if(dir[i][j]==2)
  45. {
  46. path_prnt(i-1,j);
  47. printf("add %c",ch2[j]);
  48. }
  49. else
  50. {
  51. path_prnt(i-1,j-1);
  52. if(ch1[i]!=ch2[j])
  53. printf("replace %c",ch2[j]);
  54. }
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60. int i,j;
  61. while(gets(ch1))
  62. {
  63. gets(ch2);
  64. l1=strlen(ch1);
  65. l2=strlen(ch2);
  66. for(i=0;i<l1;i++)
  67. {
  68. for(j=0;j<l2;j++)
  69. dp[i][j]=-1;
  70. }
  71. printf("%d\n",rec(l1-1,l2-1));
  72. path_prnt(l1-1,l2-1);
  73. puts("");
  74. }
  75. return 0;
  76. }
Success #stdin #stdout 0s 73472KB
stdin
Standard input is empty
stdout
Standard output is empty