【BZOJ 1355】[Baltic2009]Radio Transmission kmp

跑kmp，得到nxt數組後用n-nxt[n]就是了

#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 1000023
using namespace std;
int n,nxt[maxn],len;
char s[maxn];

void get(){
	for(int j,i=1;i<n;i++){
		j=nxt[i];
		while(j&&s[j]!=s[i])j=nxt[j];
		nxt[i+1]= s[j]==s[i] ? j+1 : 0;
	}
}

int main(){
	scanf("%d%s",&n,s);
	get();
	printf("%d",n-nxt[n]);
	return 0;
}