题目大意

给出一个字符串，输出所有既是前缀又是后缀的子串的长度。

思路

又是一道考验对KMP的next[]数组理解的题。如果清楚next[]数组的含义，那么这道题也没什么好说的了。

代码

#include<iostream>
#include<stdio.h>
using namespace std;
#define P_SIZE 1000000
int next[P_SIZE+2],res[P_SIZE];
char P[P_SIZE+2];
//P是模式串。
void COMPUTE_PREFIX_FUNCTION(char P[])
//对next[]进行赋值。 
{
	int m=strlen(P+1);
	next[1]=0;
	for(int k=0,q=2;q<=m;q++)
	{
		while(k>0&&P[k+1]!=P[q])
			k=next[k];
		if(P[k+1]==P[q])
			k++;
		next[q]=k;
	}
}
int main()
{
	while(~scanf("%s",P+1))
	{
		COMPUTE_PREFIX_FUNCTION(P);
		int total=0,len=strlen(P+1);
		res[total++]=len;
		for(int i=len;next[i]!=0;i=next[i])
			res[total++]=next[i];
		for(int i=total-1;i>=0;i--)
			printf("%d%c",res[i],i?' ':'\n');
	}
}

后记

输入那里忘记了加上“~”，导致OLE，找了好久才发现这个bug。