首页 > 代码库 > 【kmp算法】bzoj1355 [Baltic2009]Radio Transmission

【kmp算法】bzoj1355 [Baltic2009]Radio Transmission

引用题解:http://blog.csdn.net/wyfcyx_forever/article/details/40347425

#include<cstdio>#include<cstring>using namespace std;int next[1000001],n;char s[1000001];void GetFail(char P[],int next[]){    next[0]=next[1]=0;    for(int i=1;i<n;i++)      {        int j=next[i];        while(j&&P[i]!=P[j]) j=next[j];        if(P[i]==P[j]) next[i+1]=j+1;        else next[i+1]=0;      }}int main(){	scanf("%d",&n); scanf("%s",s);	GetFail(s,next);	printf("%d\n",n-next[n]);	return 0;}

【kmp算法】bzoj1355 [Baltic2009]Radio Transmission