POI 2006 OKR-Periods of Words

Solution:

Wating...

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n;
char s[N];
int Next[N];
int vis[N];
typedef long long ll;
void get_next(char p[],int lenp){
	int j=0;
	for(int i=2;i<=lenp;++i){
		while(j&&p[j+1]!=p[i])j=Next[j];
		if(p[j+1]==p[i]){j++;}
		Next[i]=j;
	}
}
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	get_next(s,n);
	ll sum=0;
	for(int i=1;i<=n;++i){
		int pos=i;
		if(Next[Next[i]]!=0){
			vis[i]=min(Next[i],vis[Next[i]]);
		}
		else{
			vis[i]=Next[i];
		}
		if(vis[i])sum+=(i-vis[i]);
	}
	printf("%lld\n",sum);
	return 0;
}