LUOGU P3435 [POI2006]OKR-Periods of Words

传送门

解题思路

首先求出kmp，那么i-nxt[i]一定是一个周期，对于每一个点一直跳nxt，跳到最小的nxt之后用i-这个nxt即为i这个前缀的答案。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

const int MAXN = 1000005;

int nxt[MAXN],n;

long long ans;

char s[MAXN];

int main(){

    scanf("%d%s",&n,s+1);

    for(register int i=2,j=0;i<=n;i++){

        while(j && s[i]!=s[j+1]) j=nxt[j];

        if(s[i]==s[j+1]) j++;

        nxt[i]=j;

    }

//  for(register int i=1;i<=n;i++) cout<<nxt[i]<<" ";

    for(register int i=1;i<=n;i++){

        int j=i;

        while(nxt[j]) j=nxt[j];

        if(nxt[i]) nxt[i]=j;

        ans+=i-j;

    }printf("%lld",ans);

    return 0;

}