LCS Medium

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e6 + 1, M = 5e3 + 1;
string s, t;
int n, m, Next[N + 1][26], f[M + 1];
void read()
{
   cin >> s >> t;
   n = s.length(); m = t.length();
   s = '?' + s;
   t = '?' + t;
}
void solve()
{
   for (int i = n + 1; i > 0; -- i)
   {
       for (int j = 0; j < 26; ++ j)
       {
           if (i == n + 1)
           {
               Next[i][j] = n + 1;
           }
           else
           {
               Next[i][j] = Next[i + 1][j];
           }
       }
       Next[i][s[i] - 'a'] = i;
   }
   fill(f + 1, f + m + 1, n + 1);
   for (int i = 1; i <= m; ++ i)
   {
       for (int j = i; j >= 1; -- j)
       {
           if (f[j - 1] == n + 1)
           {
               continue;
           }
           f[j] = min(f[j], Next[f[j - 1] + 1][t[i] - 'a']);
       }
   }
   for (int i = m; i >= 0; -- i)
   {
       if (f[i] < n + 1)
       {
           cout << i; return ;
       }
   }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        read();
        solve();
    }
}