思路

二维前缀转移，区分子串与子序列，含空串及千字符规模。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){string a,b;getline(cin,a);getline(cin,b);if(!a.empty()&&a.back()=='\r')a.pop_back();if(!b.empty()&&b.back()=='\r')b.pop_back();vector<int>p(b.size()+1),q(b.size()+1);for(char x:a){for(int j=1;j<=(int)b.size();j++)q[j]=x==b[j-1]?p[j-1]+1:max(p[j],q[j-1]);swap(p,q);}cout<<p[b.size()]<<'\n';}