开始的时候只会一个\(O(n^2log)\)
即做出所有的\(n^2\)串，显然可以用\(SAM\)来进行这样一个排序，然后\(log\)做。
但这种题我们显然要找一些友好的性质：
我们发现字符串的比较是一个从前往后的过程。
那么我们就发现如果我们选择了一个以\(i\)为开头的的串，那么如果我们把他一路选到最后一个，则答案一定不劣。
所以我们可以在\(O(n^2)\)里处理出\(Lcp\)和答案。
#include <bits/stdc++.h>
#define N 5005
using namespace std;
int T, n, Ans, f[N][N], dp[N];
char S[N];
bool compare(int x, int y) {
if (x + f[x][y] > n + 1) return false;
return S[x + f[x][y]] > S[y + f[x][y]];
}
int solve(int x, int y) {
if (!compare(x, y)) return 0;
return dp[y] + n - x - f[x][y] + 1;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %s", &n, S + 1);
for (int i = n - 1; i >= 1; --i) f[n][i] = (S[n] == S[i]);
for (int i = n - 1; i >= 1; --i)
for (int j = i - 1; j >= 1; --j)
f[i][j] = (S[i] == S[j]) ? (f[i + 1][j + 1] + 1) : 0;
dp[1] = Ans = n;
for (int i = 2; i <= n; ++i) {
dp[i] = n - i + 1;
for (int j = 1; j < i; ++j)
dp[i] = max(dp[i], solve(i, j));
Ans = max(Ans, dp[i]);
}
printf("%d\n", Ans);
}
return 0;
}