fork(4) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jAXg50
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!