///KMP算法
#include<bits/stdc++.h> using namespace std; int Next[]; void makeNext(const char P[],int next[])
{
int q,k;
int len=strlen(P);
next[]=;
for(q=,k=;q<len;q++)
{
while(k>&&P[q]!=P[k])
{
k=next[k-];
}
if(P[q]==P[k])
{
k++;
}
next[q]=k;
}
} void KMP(const char P[],const char Q[],int next[])
{
int len1,len2;
int q,k;
len1=strlen(P);
len2=strlen(Q);
makeNext(Q,next);
for(q=,k=;q<len1;q++)
{
while(k>&&P[q]!=Q[k])
{
k=next[k-];
}
if(P[q]==Q[k])
{
k++;
}
if(k==len2)
{
printf("%d\n",q-len2+);
}
}
} int main()
{
char P[]=("asdfgasbnaslk");
char Q[]=("ababab"); KMP(P,Q,Next);
int n=strlen(Q);
for(int i=;i<n;i++)
{
printf("%d ",Next[i]);
}
printf("\n");
return ;
}
KMP算法的应用
///http://poj.org/problem?id=2406
///求最小循环节
///next数组的理解与应用 //#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<stdio.h> using namespace std; char a[];
int Next[]; void makeNext(const char P[],int next[])
{
int q,k;
int len=strlen(P);
next[]=;
for(q=,k=;q<len;q++)
{
while(k>&&P[q]!=P[k])
{
k=next[k-];
}
if(P[q]==P[k])
{
k++;
}
next[q]=k;
}
} int main()
{
while(scanf("%s",a)&&strcmp(a,".")!=)
{
int l=strlen(a);
makeNext(a,Next);
if(l%(l-Next[l-])==)
printf("%d\n",l/(l-Next[l-]));
else
printf("1\n");
}
return ;
}