Seek the Name, Seek the Fame poj-2752

    题目大意:给出一个字符串p,求所有既是p的前缀又是p的后缀的所有字符串长度,由小到大输出。

    注释:$1\le strlen(p)\le 4\cdot 10^5$。

      想法:显然,这样的所有的字符串必须满足一些性质。我们预处理出所有p的next数组。然后对于next[len],如果它的next与末尾字符相同,显然这也是一个满足条件的子串,就这样,我们一直跳next,知道==-1停止。

    最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 400000
using namespace std;
char p[N+10];
int next[N+10];
int ans[N+10];
void GetNext()//预处理next数组
{
	int pLen=strlen(p);
	int k=-1;
	int j=0;
	next[0]=-1;
	while(j<pLen)
	{
		if(k==-1||p[j]==p[k])
		{
			++k;
			++j;
			next[j]=k;
		}
		else k=next[k];
	}
}
void original()//初始化
{
	memset(next,0,sizeof next);
}
int main()
{
	while(~scanf("%s",p))
	{
		original();
		int len=strlen(p);
		GetNext();
		int cnt=0;
		int t=next[len-1];
		while(t!=-1)//递归处理
		{
			if(p[t]==p[len-1]) ans[++cnt]=t+1;
			t=next[t];
		}
		for(int i=cnt;i>=1;i--)
		{
			printf("%d ",ans[i]);
		}
		printf("%d\n",len);//不要忘记最后整体字符串也是正确的。
	}
	return 0;
}

     小结:KMP的精髓还是next数组,它的匹配过程还是次要的,重点是next数组的应用。