题意
给定一个长度为\(N\)的字符串\(S\)。
在\(S\)中找到两个互相不重叠且完全相同的连续子串，并输出它的最大长度。
题目链接：https://atcoder.jp/contests/abc141/tasks/abc141_e
数据范围
\(2 \leq N \leq 5 \times 10^3\)
思路
首先介绍Z函数（exKMP）：对于一个长度为\(n\)的字符串\(s\)（下标从\(0\)开始）。定义函数\(Z_i\)表示\(s\)和\(s[i, n - 1]\)（即以\(s_i\)开头的后缀）的最长公共前缀（LCP）的长度。\(Z\)被称为\(s\)的Z函数。特别地，\(Z[0] = 0\)。Z函数可以通过\(O(n)\)的算法求出。
回到本题。我们只需要枚举起点\(i\)，然后求出\(S[i, n - 1]\)的Z函数。然后枚举每个点\(j\)的Z函数值，取最大值即可（注意去掉重叠的情况，即\(Z[j] > j\)）。
代码
[code]#include #include #include #include using namespace std;const int N = 5010;int n;string ss;int z[N];void z_function(string s){ int n = (int)s.length(); for(int i = 1, l = 0, r = 0; i < n; i ++) { if(i r) l = i, r = i + z - 1; }}int main(){ cin >> n >> ss; int ans = 0; for(int i = 0; i < n; i ++) { string t = ss.substr(i, n - i); z_function(t); for(int j = 0; j < n - i; j ++) { if(z[j] > j) continue; ans = max(ans, z[j]); } } cout |
