BZOJ_1511_[POI2006]OKR-Periods of Words_KMP
24
题意其实是求一个最短的前后缀。
于是我们把nxt反着求，每次求最小的不为0的nxt，对于这个前缀，对答案的贡献为len-nxt[i]。
代码：
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
char w[1000050];
int nxt[1000050],cnt[1000050];
long long ans;
int main() {
scanf("%*d%s",w+1);
int i,j=0;
for(i=2;w[i];i++) {
while(j&&w[j+1]!=w[i]) j=nxt[j];
nxt[i]=(w[j+1]==w[i])?++j:0;
while(nxt[nxt[i]]) nxt[i]=nxt[nxt[i]];
if(nxt[i]) ans+=i-nxt[i];
}
printf("%lld\n",ans);
}
BZOJ_1511_[POI2006]OKR-Periods of Words_KMP
原文：https://www.cnblogs.com/suika/p/9147751.html