fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s1,s2;
  4. int a,b;
  5. int arr[100][200];
  6. int arr2[100][200];
  7.  
  8. void show(string s, int i, int j)
  9. {
  10.     if(i==0 || j==0) return;
  11.     if(arr[i][j]==arr[i][j-1]) show(s,i,j-1);
  12.     else if(arr[i][j]==arr[i-1][j]) show(s,i-1,j);
  13.     else
  14.     {
  15.         show(s,i-1,j-1);
  16.         cout << s[i-1];
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     cin >> s1 >> s2;
  23.     a=s1.length();
  24.     b=s2.length();
  25.     for(int i=1;i<=a;i++)
  26.     {
  27.         for(int j=1;j<=b;j++)
  28.         {
  29.             if(s1[i-1]==s2[j-1])
  30.             {
  31.                 arr[i][j]=arr[i-1][j-1]+1;
  32.             }
  33.             else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
  34.         }
  35.     }
  36.     cout << arr[a][b] << endl;
  37.     show(s1,a,b);
  38.     cout << endl;
  39.     cout << "Insertions: " << a-arr[a][b] << endl;
  40.     cout << "Deletions: " << b-arr[a][b] << endl;
  41.     cout << "Insertions: " << b-arr[a][b] << endl;
  42.     cout << "Deletions: " << a-arr[a][b] << endl;
  43.     string s3=s1;
  44.     reverse(s3.begin(),s3.end());
  45.     for(int i=1;i<=a;i++)
  46.     {
  47.         for(int j=1;j<=a;j++)
  48.         {
  49.             if(s1[i-1]==s3[j-1])
  50.             {
  51.                 arr2[i][j]=arr2[i-1][j-1]+1;
  52.             }
  53.             else arr2[i][j]=max(arr2[i-1][j],arr2[i][j-1]);
  54.         }
  55.     }
  56.     cout << "Length of longest palindromic subsequence: " << arr2[a][a] << endl;
  57.     if(arr[a][b]==s1.length()) cout << "Yes" << endl;
  58.     else cout << "NO" << endl;
  59. }
  60.  
  61. /*
  62. if
  63.     x[i]==y[j]->lcs(x[i-1],y[j-1])+1
  64. else
  65.     max(lcs(i-1,j),lcs(i,j-1))
  66. */
  67.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0

Insertions: 0
Deletions: 0
Insertions: 0
Deletions: 0
Length of longest palindromic subsequence: 0
Yes
https://ideone.com/hrYVyw
language:
C++ (gcc 8.3)
created:
5 days 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!