给定长 $n,m$ 的序列 $a,b$，求 $a,b$ 的 LCS。

$n \le 5 \times 10^3, m \le 5 \times 10^5$，仅由大写字母构成。

感觉自己想的 dp 没什么错的，过了样例，但其他数据都是输出 0.

#include <bits/stdc++.h>
#define N 5005
#define M 500005
#define C 30
using namespace std;

int n, m;
char a[N], b[M];
int dp[N][N];
// dp[i][k]：a的前i个与b的lcs长度为k时，b的最短前缀长度
int nxt[C][M];  // nxt[c][j]：b[j+1:]中下一个c的出现点
vector<int> mp[C];

const int inf = 0x3f3f3f3f;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> (a + 1) >> (b + 1);
	n = strlen(a + 1), m = strlen(b + 1);
	for (int i = 1; i <= m; i++) mp[b[i] - 'A' + 1].emplace_back(i);
	for (int i = 0; i <= m; i++) {
		for (char c = 'A'; c <= 'Z'; c++) {
			int x = c - 'A' + 1;
			auto it = upper_bound(mp[x].begin(), mp[x].end(), i);
			if (it == mp[x].end()) nxt[x][i] = inf;
			else nxt[x][i] = *it;
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i <= n; i++) dp[i][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= i; k++) {
			dp[i][k] = dp[i - 1][k];  // 不选a[i]
			if (dp[i][k - 1] < inf)
				dp[i][k] = min(dp[i][k], nxt[a[i] - 'A' + 1][dp[i][k - 1]]); // 选a[i]
		}
	}
	for (int k = n; k >= 1; k--) {
		for (int i = 1; i <= n; i++) {
			if (dp[i][k] < inf) return cout << k, 0;
		}
	}
	cout << 0;
	return 0;
}