fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string lcs(string &x,string &y)
  4. {
  5.     int m=x.length(),n = y.length(),lcs_size;
  6.     int a[m+1][n+1];
  7.     for(int i=0;i<=m;i++)
  8.     {
  9.         for(int j=0;j<=n;j++)
  10.         {
  11.             if(i==0 || j==0)
  12.             a[i][j]=0;
  13.             else
  14.             if(x[i-1]==y[j-1])
  15.             a[i][j]=1+a[i-1][j-1];
  16.             else
  17.             a[i][j]=max(a[i-1][j],a[i][j-1]);
  18.         }
  19.     }
  20.     lcs_size=a[m][n];
  21.     int i=m,j=n,k;
  22.     string l="",scs="";
  23.     while(i>0 && j>0)
  24.     {
  25.         if(x[i-1]==y[j-1])
  26.         {
  27.             l.push_back(x[i-1]);
  28.             i--;
  29.             j--;
  30.         }
  31.         else
  32.         if(a[i-1][j]>a[i][j-1])
  33.         i--;
  34.         else
  35.         j--;
  36.     }
  37.     reverse(l.begin(),l.end());
  38.     i=0,j=0,k=0;
  39.     while(i<x.size() && j<y.size() && k<l.size())
  40.     {
  41.       if(x[i]==l[k] && y[j]==l[k])
  42.       {
  43.         //cout<<x[i];
  44.         scs.push_back(x[i]);
  45.         i++;
  46.         j++;
  47.         k++;
  48.       }
  49.       else
  50.       if(x[i]==l[k] && y[j]!=l[k])
  51.       {
  52.         //cout<<y[j];
  53.         scs.push_back(y[j]);
  54.         j++;
  55.       }
  56.       else
  57.       if(x[i]!=l[k] && y[j]==l[k])
  58.       {
  59.         //cout<<x[i];
  60.         scs.push_back(x[i]);
  61.         i++;
  62.       }
  63.       else
  64.       {
  65.         //cout<<x[i]<<y[j];
  66.         scs.push_back(x[i]);
  67.         scs.push_back(y[j]);
  68.         i++;
  69.         j++;
  70.       }
  71.     }
  72.     while(i<x.size())
  73.     {
  74.       //cout<<x[i];
  75.         scs.push_back(x[i]);
  76.       i++;
  77.     }
  78.     while(j<y.size())
  79.     {
  80.       //cout<<y[j];
  81.         scs.push_back(y[j]);
  82.       j++;
  83.     } 
  84.     //cout<<endl;
  85.     return scs;
  86. }
  87. int main()
  88. {
  89.     ios_base::sync_with_stdio(false);
  90.     cin.tie(NULL);
  91.     int t;
  92.     cin>>t;
  93.     while(t--)
  94.     {
  95.         int k;
  96.         cin>>k;
  97.         vector <string> v(k);
  98.         for(int i=0;i<k;i++)
  99.             cin>>v[i];
  100.         if(k==1)
  101.             cout<<v[0]<<endl;
  102.         else
  103.         {
  104.             string r = lcs(v[0],v[1]);
  105.             for(int i=2;i<k;i++)
  106.                 r = lcs(r,v[i]);
  107.             cout<<r<<endl;
  108.         }
  109.     }
  110.     return 0;
  111. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
3
2
BG
GB
2
BGB
GG
3
BG
GBB
BGB
stdout
copy 
BGB
BGBG
BGBB
https://ideone.com/Qyaw2Y
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!