BZOJ P1355: [Baltic2009]Radio Transmission

ans=n-next[n]

這是kmp算法的性質，ans就是循環節的長度

下面是代碼

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n;
char ch[1000003];
int next[1000003];
int j,ans=100000000;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ch[i];
	}
	for(int i=2;i<=n;i++){
		while(j&&ch[j+1]!=ch[i]){
			j=next[j];
		}
		j+=ch[j+1]==ch[i];
		next[i]=j;
	}
	cout<<n-next[n];
	return 0;
}
/*
in:
8
cabcabca

out:
3
*/