本文主要是介绍poj 2752 (summerIII seek the name,seek the fame)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题真的加深了我对next数组的理解,。没想除了用在KMP上还能有这种操作。。。开始想着用其中的K的值做，因为根据定义，k代表的是最长相同的前后缀长度。。。然后不知道为什么WA。。。。后来百度了一下别人的做法恍然大悟，觉得精妙无比。就是通过递归next数组然后求得前后缀的长度。
以下为链接 点击打开链接
AC代码：
#include<cstdio>
#include<cstring>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=400000+50;
char str[maxn];
int sum[maxn],next[maxn],num;
void makeNext(const char P[],int next[])
{int q,k;int m=strlen(P);next[0]=0;for(q=1,k=0;q<m;++q){while(k>0&&P[q]!=P[k])k=next[k-1];if(P[q]==P[k])k++;next[q]=k;}for(int i=m;i>0;){num++;//cout<<"next:"<<next[i-1]<<endl;sum[num]=next[i-1];///每次都忘记这里要减一，字符串最后一位为‘\0’;i=next[i-1];}
}int main()
{while(scanf("%s",str)!=EOF){int len=strlen(str);num=0;memset(next,0,sizeof(next));memset(sum,0,sizeof(sum));makeNext(str,next);for(int i=num-1;i>=1;i--)printf("%d ",sum[i]);printf("%d\n",len);}return 0;
}
这篇关于poj 2752 (summerIII seek the name,seek the fame)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
