POJ 2752
描述
小猫非常著名,很多夫妇Byteland翻山越岭,并要求新生的小猫的名字给他们的孩子。他们寻求的名字,同时寻求名声。为了摆脱这种无聊的工作,创新的小猫是一个简单但神奇的算法:
步骤1。把父亲的名字,母亲的名字,一个新的字符串。
步骤2。找到一个合适的prefix-suffix串年代(不仅是前缀,后缀的年代还)。
例子:父亲=“阿拉巴马州”,母亲=‘拉’,我们有年代=“阿拉巴马”+“la”=“alala”。潜在的年代prefix-suffix字符串{ ' a ',“阿拉巴马州”,“alala”}。给定的字符串,你能帮助小猫编写一个程序来计算可能的年代prefix-suffix字符串的长度吗?(他会谢谢你给你的宝宝一个名字:)
输入
输入包含一个测试用例的数量。每个测试用例占一行,包含上述字符串年代。
/********************************* author : Grant Yuan algorithm; kmp source : POJ 2752 time ；2014/10/3 20:38 *********************************/ #include
<iostream>
#include
<cstdio>
#include
<cstring>
#include
<cstdlib>
#include#define MAX 400007using namespace std;int next[MAX];char s[MAX];int ans;int l;int sum[MAX];void get_next(){ next[0]=-1; int j=-1; int i=0; while(i
<l){ if(j="=-1||s[j]==s[i])" {="" i++;j++;="" next[i]="j;" }="" else="" j="next[j];" }}int="" main(){="" while(~scanf("%s",s)){="" int="" j;="" memset(sum,0,sizeof(sum));="" l="strlen(s);" get_next();="" k="0;" for(int="" i="k-2;i" sum[k++]="next[i];">
=0;--i) printf("%d ",sum[i]); printf("%d/n",l);} return 0;}
</l){>
</cstdlib>
</cstring>
</cstdio>
</iostream>//源代码片段来自云代码http://yuncode.net