算法
(动态规划) $O(n^2)$
记 dp[i][j]
表示从 $S$ 的第 $i$ 个字符开始的后缀和从 $S$ 的第 $j$ 个字符开始的后缀的 $\operatorname{lcp}$ 的 长度
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int dp[5005][5005];
int main() {
int n;
string s;
cin >> n >> s;
for (int i = n-1; i >= 0; --i) {
for (int j = n-1; j >= 0; --j) {
if (s[i] != s[j]) dp[i][j] = 0;
else dp[i][j] = dp[i+1][j+1]+1;
}
}
int ans = 0;
rep(i, n)rep(j, n) {
if (i >= j) continue; // i < j
int now = min(dp[i][j], j-i);
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}