http://poj.org/problem?id=2752
分析：
题目要求一个既是S的前缀又是S的后缀的子串（S本身是自己的前缀又是自己的后缀）。主要利用next数组求解。
e.g.
|
no |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
S |
a |
b |
a |
b |
c |
a |
b |
a |
b |
a |
b |
a |
b |
c |
a |
b |
a |
b |
/0 |
|
next |
-1 |
0 |
0 |
1 |
2 |
0 |
1 |
2 |
3 |
4 |
3 |
4 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Out: 2 4 9 18
由于子串既是S的前缀又是后缀，所以除去字符串本身长度18外，次长的为在字符串结束符‘\0’处求得的next数组值9，
此时S的前缀为 ababcabab(012345678)，S的后缀为 ababcabab(9-17)。接着找第三长的既是S的前缀又是S后缀的子串。
如果找next[17]处的值8，则不满足是S后缀的要求，因为17本身的字符是被排除在外的，10-16亦是同理。
而对于9之前的子串有next[18]知既是S的前缀又是S的后缀。而next[9]的值4指明了位置在9前的子串的前后缀长度为4，
而该子串包含在S的前缀中，所以该子串的后缀也包含在S的前缀中，而S的前缀又是S的后缀，所以该子串的后缀也是S的后缀。
依次往前直到满足条件的子串长度为0为止。
代码：
//seek the name,seek the fame
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
#define MAXN 400004
int plen;
int next[MAXN]; //MAXN模式串长度
char pat[MAXN];
void getNext()
{
int j=0, k=-1;
next[0]=-1;
while(j<plen){ //计算模式串每一个位置j的next[j]值
while(k>-1 && pat[j]!=pat[k]) k=next[k];
next[++j]=++k;
}
}
void show(int n)
{
if(next[n]>0){
show(next[n]);
printf("%d ",next[n]);
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(cin>>pat){
plen=strlen(pat);
getNext();
show(plen);
cout<<plen<<endl;
}
return 0;
}
poj_2752 Seek the Name, Seek the Fame
原文：http://blog.csdn.net/vuorange/article/details/39274179