fork(8) download
copy 
  1. // An LCS based program to find minimum number insertions needed to
  2. // make a string palindrome
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cstdlib>
  6.  
  7. /* Utility function to get max of 2 integers */
  8. int max(int a, int b)
  9. {   return (a > b)? a : b; }
  10.  
  11. //this method uses only 2 arrays of length of string ** space optimization**
  12. int lcs(char *str1,char *str2,int n,int m)
  13. {
  14.  
  15. 	int len1,len2,i,j;
  16. 	len1=n;
  17. 	len2=m;
  18. 	int *x=new int[max(len1,len2)+1];
  19. 	int *y=new int[max(len1,len2)+1];
  20.  
  21. 	for(i=0;i<=len1;i++)
  22. 		y[i]=x[i]=0;
  23.  
  24. 	for(i=1;i<=len1;i++)
  25. 	{
  26. 		for(j=1;j<=len2;j++)
  27. 		{
  28. 			if(str1[i-1]==str2[j-1])
  29. 				y[j]=x[j-1]+1;
  30. 			else
  31. 				y[j] = y[j-1] > x[j] ? y[j-1] : x[j];
  32. 		}
  33. 		int * t;
  34. 		t = x;
  35. 		x = y;
  36. 		y = t;
  37. 	}
  38.  
  39. 	int len=x[n];
  40. 	delete x;
  41. 	delete y;
  42.  
  43. 	return len;
  44. }
  45.  
  46. // LCS based function to find minimum number of insersions
  47. int findMinInsertionsLCS(char str[], int n)
  48. {
  49.    // Creata another string to store reverse of 'str'
  50.    char rev[n+1];
  51.    strcpy(rev, str);
  52.    int i=0,j=n-1;
  53.    while(i<j)
  54.    {
  55.    		char tmp=rev[i];
  56.    		rev[i]=rev[j];
  57.    		rev[j]=tmp;
  58.    		i++;
  59.    		j--;
  60.    }
  61.  
  62.    return (n - lcs(str, rev, n, n));
  63. }
  64.  
  65. // Driver program to test above functions
  66. int main()
  67. {
  68.     char str[] = "geeks";
  69.     printf("%d", findMinInsertionsLCS(str, strlen(str)));
  70.     return 0;
  71. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/RJnWq9
language:
C++ (gcc 8.3)
created:
9 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!