fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 105;
  5.  
  6. int main()
  7. {
  8.     freopen("LCS.INP", "r", stdin);
  9.     freopen("LCS.OUT", "w", stdout);
  10.  
  11.     string X, Y;
  12.     cin >> X >> Y;
  13.  
  14.     X = " " + X;
  15.     Y = " " + Y;
  16.  
  17.     int m = X.size() - 1;
  18.     int n = Y.size() - 1;
  19.  
  20.     int f[MAX][MAX] = {0};
  21.     int dx[MAX] = {0}, dy[MAX] = {0};
  22.  
  23.     for (int i = 1; i <= m; i++)
  24.     {
  25.         for (int j = 1; j <= n; j++)
  26.         {
  27.             if (X[i] == Y[j])
  28.             {
  29.                 f[i][j] = f[i - 1][j - 1] + 1;
  30.             }
  31.             else
  32.             {
  33.                 f[i][j] = max(f[i - 1][j], f[i][j - 1]);
  34.             }
  35.         }
  36.     }
  37.  
  38.     int i = m, j = n;
  39.     while (i > 0 && j > 0)
  40.     {
  41.         if (X[i] == Y[j])
  42.         {
  43.             dx[i] = 1;
  44.             dy[j] = 1;
  45.             i--;
  46.             j--;
  47.         }
  48.         else if (f[i][j] == f[i - 1][j])
  49.         {
  50.             i--;
  51.         }
  52.         else
  53.         {
  54.             j--;
  55.         }
  56.     }
  57.  
  58.     for (int i = 1; i <= m; i++)
  59.     {
  60.         if (dx[i] == 1)
  61.         {
  62.             cout << X[i];
  63.         }
  64.     }
  65.     cout << endl;
  66.  
  67.     for (int i = 1; i <= m; i++)
  68.     {
  69.         if (dx[i] == 1)
  70.         {
  71.             cout << i << " ";
  72.         }
  73.     }
  74.     cout << endl;
  75.  
  76.     for (int i = 1; i <= n; i++)
  77.     {
  78.         if (dy[i] == 1)
  79.         {
  80.             cout << i << " ";
  81.         }
  82.     }
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KpkHRJ
language:
C++ (gcc 8.3)
created:
3 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!