看到题目的要求，有一个特别 naive 的想法：f[i] 表示 从 i 往前跳不为零的 nxt，直到不能跳，能跳到的位置
然后各种乱搞判断什么的
其实不用
考虑一下 kmp 的基本定义
对于 i 这个前缀，f[i] 这个前缀是它的一个后缀
你把它放在后缀的位置上一看，这不就是题目要求的吗
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
int n;
int nxt[MAXN], f[MAXN];
char str[MAXN];
ll ans;
inline void getnxt() {
nxt[0] = nxt[1] = 0;
for(int i = 1; i < n; ++i) {
int j = nxt[i];
while(j && str[i] != str[j]) j = nxt[j];
nxt[i + 1] = (str[i] == str[j]) ? j + 1 : 0;
}
return;
}
int main() {
scanf("%d", &n); scanf("%s", str);
getnxt();
for(int i = 1; i <= n; ++i) {
f[i] = f[nxt[i]] ? f[nxt[i]] : nxt[i];
if(f[i]) ans += i - f[i];
}
printf("%lld\n", ans);
return 0;
}
BZOJ1511: [POI2006]OKR-Periods of Words
原文：https://www.cnblogs.com/xcysblog/p/9602471.html