fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define el '\n'
  4. #define oo LLONG_MAX >> 2
  5. #define all(x) x.begin(), x.end()
  6. #define allr(x) x.rbegin(), x.rend()
  7. #define pb push_back
  8. #define pep_Guardiola                                                          \
  9.   ios::sync_with_stdio(0);                                                     \
  10.   cin.tie(0);                                                                  \
  11.   cout.tie(0);
  12. using namespace std;
  13.  
  14. signed main() {
  15.   pep_Guardiola
  16.  
  17.       string s,
  18.       t;
  19.   cin >> s >> t;
  20.   if (s.size() > t.size())
  21.     swap(s, t);
  22.   int n = s.size(), m = t.size();
  23.   vector<vector<int>> nxt(m + 1, vector<int>(26, oo));
  24.   nxt[m - 1][t[m - 1] - 'a'] = m - 1;
  25.   for (int i = m - 1; i >= 0; i--)
  26.     nxt[i] = nxt[i + 1], nxt[i][t[i] - 'a'] = i + 1;
  27.   vector<int> dp(n + 2, oo);
  28.   dp[0] = 0;
  29.   for (int i = 1; i <= n; i++)
  30.     for (int len = i; len >= 1; len--)
  31.       if (dp[len - 1] != oo)
  32.         dp[len] = min(dp[len], nxt[dp[len - 1]][s[i - 1] - 'a']);
  33.   int ans = 0;
  34.   for (int len = 0; len <= n; len++)
  35.     if (dp[len] != oo)
  36.       ans = len;
  37.   cout << ans;
  38. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
bacaad
dadfcecf
stdout
copy 
2
https://ideone.com/sTCAtv
language:
C++ (gcc 8.3)
created:
1 day 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!