KMP继续练手.题目问的是一个串前缀等于后缀的可能长度是哪些,输出来.题目考的是对KMP失配指针的理解,当最后一位失配(即'\0'那里)时,指针会移动到前缀对应匹配的部分,所以这个长度是我们要的,然后接着这个新的前缀的失配指针移到的部分,与这个前缀的后缀也是匹配的..这样一直滚下去就可以了得到所有可能的值.
贴一记代码.
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define mxp 400050 int f[mxp+50];
char P[mxp+50]; void getFail(const char *P,int *f)
{
int m=strlen(P);
f[0]=f[1]=0;
for(int i=1;i<m;++i){
int j=f[i];
while(j&&P[i]!=P[j]) j=f[j];
f[i+1]= P[i]==P[j]? j+1:0;
}
} int main()
{
while(scanf("%s",P)!=EOF)
{
getFail(P,f);
int n=strlen(P);
vector<int> ans;
while(n){
ans.push_back(n);
n=f[n];
}
reverse(ans.begin(),ans.end());
printf("%d",ans[0]);
for(int i=1;i<ans.size();++i){
printf(" %d",ans[i]);
}
puts("");
}
return 0;
}