fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp> // Common file
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/detail/standard_policies.hpp>
  6. #include <functional> // for less
  7. #include <iostream>
  8. using namespace __gnu_pbds;
  9. void __print(int x) {cerr << x;}
  10. void __print(long x) {cerr << x;}
  11. void __print(long long x) {cerr << x;}
  12. void __print(unsigned x) {cerr << x;}
  13. void __print(unsigned long x) {cerr << x;}
  14. void __print(unsigned long long x) {cerr << x;}
  15. void __print(float x) {cerr << x;}
  16. void __print(double x) {cerr << x;}
  17. void __print(long double x) {cerr << x;}
  18. void __print(char x) {cerr << '\'' << x << '\'';}
  19. void __print(const char *x) {cerr << '\"' << x << '\"';}
  20. void __print(const string &x) {cerr << '\"' << x << '\"';}
  21. void __print(bool x) {cerr << (x ? "true" : "false");}
  22.  
  23. template<typename T, typename V>
  24. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  25. template<typename T>
  26. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  27. void _print() {cerr << "]\n";}
  28. template <typename T, typename... V>
  29. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  30. #ifndef ONLINE_JUDGE
  31. #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
  32. #else
  33. #define  dbg(x...)
  34. #endif
  35. #define EACH(x, a) for (auto& x: a)
  36. template<class A> void read(vector<A>& v);
  37. template<class A, size_t S> void read(array<A, S>& a);
  38. template<class T> void read(T& x) {
  39.     cin >> x;
  40. }
  41. void read(double& d) {
  42.     string t;
  43.     read(t);
  44.     d = stod(t);
  45. }
  46. void read(long double& d) {
  47.     string t;
  48.     read(t);
  49.     d = stold(t);
  50. }
  51. template<class H, class... T> void read(H& h, T&... t) {
  52.     read(h);
  53.     read(t...);
  54. }
  55. template<class A> void read(vector<A>& x) {
  56.     EACH(a, x)
  57.     read(a);
  58. }
  59. template<class A, size_t S> void read(array<A, S>& x) {
  60.     EACH(a, x)
  61.     read(a);
  62. }
  63. template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2> &a) {in >> a.first >> a.second; return in;}
  64. template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> a) {out << a.first << " " << a.second; return out;}
  65. template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
  66. template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}
  67. #define sc(n)                        scanf("%d",&n)
  68. #define scc(n)                       scanf("%c",&n)
  69. #define sl(n)                       scanf("%lld",&n)
  70. #define sf(n)                       scanf("%lf",&n)
  71. #define ll long long
  72. #define vl vector<ll>
  73. #define pb                push_back
  74. #define ppb               pop_back
  75. #define pf                push_front
  76. #define mp make_pair
  77. #define ppf               pop_front#define mp make_pair
  78. #define f(i, l, r) for(ll i = int(l); i < int(r); i++)
  79. #define fr(i, l, r) for(ll i = int(l); i >= int(r); i--)
  80. #define fi first
  81. #define se second
  82. #define rsz resize
  83. #define cnl cout << "\n"
  84. #define all(x) x.begin(), x.end()
  85. #define allr(x) x.rbegin(), x.rend()
  86. #define sz(x) ((int)x.size())
  87. #define ln(x) ((int)x.length())
  88. #define setbits(x)  __builtin_popcountll(x)
  89. #define clr(x,v) memset(x, v, sizeof(x))
  90. #define endl "\n"
  91. #define rt return
  92. #define ins insert
  93. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  94. typedef pair<ll, ll> pll;
  95. #define uml unordered_map<ll,ll>
  96. #define vpl vector <pll >
  97. typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  98. #define ld long double
  99. #define vt vector
  100. const int MAXN = 1e6 + 500000;
  101. ll mod = 1e9 + 7;
  102. ll dx[] = {0, -1, 1, 0, -1, -1, 1, 1};
  103. ll dy[] = {1, 0, 0, -1, 1, -1, -1, 1};
  104. string a, b, c;
  105. vl lps;
  106. ll dp[103][103][103];
  107. ll go(ll i, ll j, ll match) {
  108.     if (match == ln(c)) return INT_MIN;
  109.     if (i == ln(a) || j == ln(b)) {
  110.         return 0;
  111.     }
  112.     if (dp[i][j][match] != -1)return dp[i][j][match];
  113.     ll ans = 0;
  114.     if (a[i] == b[j]) {
  115.         ll cc = match;
  116.         while (cc > 0 && a[i] != c[cc]) cc = lps[cc - 1];
  117.         if (a[i] == c[cc]) cc++;
  118.         ans = max(ans, 1 + go(i + 1, j + 1, cc));
  119.     }
  120.     ans = max(ans, go(i + 1, j, match));
  121.     ans = max(ans, go(i, j + 1, match));
  122.     return dp[i][j][match] = ans;
  123. }
  124.  
  125. void solve() {
  126.     cin >> a >> b >> c;
  127.     lps.assign(ln(c) + 1, 0);
  128.     ll j = 0;
  129.     f(i, 1, ln(c)) {
  130.         while (j > 0 && c[i] != c[j]) j = lps[j - 1];
  131.         if (c[i] == c[j]) j++;
  132.         lps[i] = j;
  133.     }
  134.     clr(dp, -1);
  135.     ll ans = go(0, 0, 0);
  136.     string s = "";
  137.     ll match = 0;
  138.     ll i = 0; j = 0;
  139.     while (i < ln(a) && j < ln(b) && match != ln(c)) {
  140.         if (a[i] == b[j]) {
  141.             ll cc = match;
  142.             while (cc > 0 && a[i] != c[cc]) cc = lps[cc - 1];
  143.             if (a[i] == c[cc]) cc++;
  144.             if (ans == 1 + go(i + 1, j + 1, cc)) {
  145.                 s += a[i];
  146.                 ans -= 1;
  147.                 match = cc;
  148.                 i++, j++;
  149.                 continue;
  150.             }
  151.         }
  152.         if (ans == go(i + 1, j, match)) i++;
  153.         else if (ans == go(i, j + 1, match)) j++;
  154.     }
  155.     assert(ans == 0);
  156.     if (ln(s) == 0) {
  157.         cout << 0 << endl;
  158.         rt;
  159.     }
  160.     cout << s << endl;
  161. }
  162.  
  163. signed main() {
  164. // #ifndef ONLINE_JUDGE
  165. //     freopen("input.txt", "r", stdin);
  166. //     freopen("output.txt", "w", stdout);
  167. // #endif
  168.     ios_base::sync_with_stdio(false);
  169.     cin.tie(NULL); cout.tie(NULL);
  170.     int T = 1;
  171.     // cin >> T;
  172.     while (T--) {
  173.         solve();
  174.     }
  175. }
Success #stdin #stdout 0.01s 12072KB
comments (?)
stdin
copy 
AAAAAAAABCA
ABCA
CA
stdout
copy 
ABC
https://ideone.com/5iQzMa
language:
C++14 (gcc 8.3)
created:
2 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!