fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define st first
  4. #define nd second
  5. using namespace std;
  6. set <string> v;
  7. string s1,s2;
  8. struct edge
  9. {
  10.     string s;
  11.     ll pos1,pos2;
  12. };
  13. map <string,ll> _cnt;
  14. const ll maxn=81;
  15. ll n,m;
  16. ll dp[maxn][maxn];
  17. ll cnt=0;
  18. vector <edge> danhsach[maxn];
  19. int main()
  20. {
  21.     cin>>s1>>s2;
  22.     s1=' '+s1;
  23.     s2=' '+ s2;
  24.     n=s1.size();
  25.     m=s2.size();
  26.     for (ll i=1;i<=n;i++)
  27.     for (ll j=1;j<=m;j++){
  28.         if (s1[i]==s2[j])
  29.         {
  30.             dp[i][j]=dp[i-1][j-1]+1;
  31.             string _st="";
  32.             _st+=s1[i];
  33.             if (dp[i][j]==1)
  34.             danhsach[dp[i][j]].push_back({_st,i,j});
  35.             else
  36.                 for (edge it:danhsach[dp[i][j]-1])
  37.             {
  38.                 string s=it.s;
  39.                 ll _i=it.pos1,_j=it.pos2;
  40.                 if (_i<i and _j<j)
  41.                 {
  42.                     string _s=s+s1[i];
  43.                     danhsach[dp[i][j]].push_back({_s,i,j});
  44.                 }
  45.             }
  46.         }
  47.         else
  48.             dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
  49.         cnt=max(cnt,dp[i][j]);
  50.     }
  51.     for (edge it:danhsach[cnt])
  52.     {
  53.         v.insert(it.s);
  54.     }
  55.     cout<<v.size()<<'\n';
  56.     for (ll i=danhsach[cnt].size()-1;i>=0;i--)
  57.     {
  58.         if (!_cnt[danhsach[cnt][i].s])
  59.         {
  60.         _cnt[danhsach[cnt][i].s]=1;
  61.         cout<<danhsach[cnt][i].s<<'\n';
  62.         }
  63.     }
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/qvbkRn
language:
C++14 (gcc 8.3)
created:
13 hours 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!