题目大意
给定若干字符串（这些字符串总长 \(≤ 4 × 10^5\)），在每个字符串中求出所有既是前缀又是后缀的子串长度。
例如：ababcababababcabab，既是前缀又是后缀的：ab，abab，ababcabab，ababcababababcabab。
解题思路
显然是 KMP 模板。
有关 KMP 的内容，可参考我的博客，点这里。
为什么这与 KMP 有关系呢，大家还记得 KMP 中的 next 数组吗？
\(next_i\) 为从 \(p_0\) 往后数，同时从 \(p_i\) 往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。
给出一个例子：
这是一个字符串 -------，一共 \(7\) 位。
若 \(next_6=3\)，此时可得出原题的一个答案。
字符串即为 $$$-$$$。
由 next 的定义可得，\(p[0,2]=p[4,6]\)。
假设 \(next_{next_6}=next_3=1\)，则 \(p_0=p_2\) 原字符串变为 #$#-$$$，因为 \(p[0,2]=p[4,6]\)，字符串又变为 #$#-#$#，因为 \(p_0=p_6\)，所以 \(1\) 又是一个答案。
于是得出，直接跳 next 就行了。
最后升序输出。
回顾解题思路，根据 next 的定义进行模拟，最后得出结论。
AC CODE
#include <bits/stdc++.h>
using namespace std;
int a[1000005], ans, pmt[1000005];
string s, p;
int main()
{
while(cin >> s)
{
pmt[0] = pmt[1] = 0;
int cnt = 0;
for (int i = 1, j = 0; i < s.length(); ++i)
{
while (s[i] != s[j] && j >= 0)
j = j ? pmt[j - 1] : -1;
pmt[i + 1] = ++j;
}
// for(int i = 1; i <= s.length(); ++i) cout << pmt[i] << " ";
// cout << endl;
int n = s.length();
a[++cnt] = n;
while(pmt[n])
{
a[++cnt] = pmt[n];
n = pmt[n];
}
for(int i = cnt; i >= 1; --i)
{
printf("%d ", a[i]);
}
printf("\n");
}
return 0;
}