题目大意
给出一个字符串，输出所有既是前缀又是后缀的子串的长度。
思路
又是一道考验对KMP的next[]数组理解的题。如果清楚next[]数组的含义，那么这道题也没什么好说的了。
代码
#include
#include
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;q0&&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。