对Next数组的认识
Next数组是对于模式串来说的，简单的来说就是一个串，假设有前缀和后缀相等的情况 （字符串的前缀是指字符串的任意首部。比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”。同样，字符串的任意尾部是字符串的后缀，“abbc”的后缀有“c”,“bc”,“bbc”,“abbc”。）
那么当Next数组不为零的时候就是前一个字符和前缀匹配到了
而Next数组的值就是匹配到字符的长度。
当Next[Next]就是Next进行回溯的时候，意思就是当前位置和前缀匹配到的长度的上一个阶段。还是我们之前的那个字符串，假设我们把末尾加一个a，很显然这时候的最后一个Next的值为4，那么我们现在来看Next4,很清晰的可以看出来是1，这就说明此时有一个后缀和前缀匹配，
不太清楚也可以再加长一些
Next数组寻找的时候就是找到一个位置（假设现在下标来到了9），往前数，找到第一个和前缀第一个字符相同的字符（上图中就是下标为6的位置），此时的位置就是Next数组的第一个阶段（值为4也就是Next[Next[9]])，如果接着继续往前找那么最后的值就是下标在9的时候后缀能和前缀匹配到的最小长度（在上图也即是1）。
第一题（Oulipo ）
HDU - 1686
题目大意：给一个主串一个模式串，计算主串中模式串出现了多少次（可重叠）
注意匹配过之后直接指向当前位置
include
include
include
include
include
const int maxn=1e6+10;
using namespace std;
int Next[maxn];
char str[maxn],mo[maxn];
int ans;
void getNext()
{
int i=0;
int j=-1;
int len=strlen(mo);
while(i<len)
{
if(j==-1||mo[i]==mo[j])
{
i++;
j++;
Next[i]=j;
}
else
j=Next[j];
}}
int kmp()
{
int i,j;
int ans=0;
i=j=0;
int l1=strlen(str);
int l2=strlen(mo);
while(i<l1)
{
while(j!=-1&&str[i]!=mo[j]) j=Next[j];
i++;j++;
if(j>=l2)
{
ans++;
j=Next[j];
}
}
return ans;}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%s%s",mo,str);
Next[0]=-1;
getNext();
printf("%d\n",kmp());
}
return 0;}
第二题（剪花布条）
HDU - 2087
题目大意：给一个主串一个模式串，计算主串中模式串出现了多少次（不可重叠）
首先计算出模式串的Next数组，然后kmp进行匹配就可以了，注意一点就是在完成一次匹配后应该将模式串指向，上次匹配结束的下一个位置
include<bits/stdc++.h>
using namespace std;
char s[2010],p[2012];
int nex[2021];
int ans;
int getnext(char *p,int nex[])
{
int p_len=strlen(p);
nex[0]=-1;
int k=-1;
int j=0;
while(j<p_len-1)
{
if(k==-1||p[j]==p[k])
{
++j;
++k;
nex[j]=k;
}
else
k=nex[k];
}}
void kmp(char s,char p)
{
int l=-1;
int s_len=strlen(s),p_len=strlen(p);
getnext(p,nex);
int j=0;
for(int i=0; i<s_len; i++)
{
while(j&&s[i]!=p[j]) j=nex[j];
if(s[i]==p[j]) j++;
if(j==p_len)
{
if(i-l>=p_len)
{
ans++;
l=i;
}
}
}}
int main()
{
while(cin>>s)
{
if(s[0]=='#') break;
cin>>p;
getchar();
ans=0;
kmp(s,p);
cout<<ans<<endl;
}}
第三题（ Seek the Name, Seek the Fame ）
POJ - 2752
题目大意：给一个字符串，找到所有前后缀的长度
解题思路：通过Next数组的性质，我们知道，Next数组的值就是当前能匹配到前缀的最大长度，回到题目，也就是说，将每个Next数组的值输出，由此得出答案
include
include
include
using namespace std;
const int N=1e6+5;
int Next[N];
char s[N];
char p[N];
void getnext(char *p)
{
Next[0]=-1;
int p_len=strlen(p);
int j=0;
int k=-1;
while(j<p_len)
{
if(k==-1||p[j]==p[k])
{
k++;
j++;
Next[j]=k;
}
else
{
k=Next[k];
}
}
}
int a[N];
int main()
{
while(scanf("%s",p)!=EOF)
{
memset(a,0,sizeof(a));
getnext(p);
int l=0;
int ans=strlen(p);
while(Next[ans]!=0)
{
a[l++]=Next[ans];
ans=Next[ans];
}
for(int i=l-1; i>=0; i--)
cout<<a[i]<<" ";
cout<<strlen(p)<<endl;
}}
