標簽：
題目描述
給出一個字符串，求出存在多少子串，使得這些子串既是主串的前綴，又是主串的後綴。從小到大依次輸出這些子串的長度。
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
解題思路：
我们首先知道最大的那个数肯定是主串本身的长度。除去这个最大的应该是next[len].由于我们肯定是由大往小找，而题目要求输出时从小到大输出，所以考虑使用栈结构。找到了next[len]后，主串的前后都有一段长度为next[len]的相同串，故我们考虑next[ next[len] ] 即考虑前缀这边的相同前后缀，由next性质可以知道，前缀的后缀就是后缀的后缀，所以也就是原主串的更小的前后缀相同。
所以一直遞歸下去就可以了，直到next=0爲止。
需要注意的是，next數組不能開優化，應該給予next最本質的定義，否則會出錯。
代碼如下
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
int k = -1;//k记录的是next[j]
next[0] = k;
int j = 0;
while (j < pLen) {
/** next[j]=-1时,next[j+1]肯定是0;p[j]=p[k]时,next[j+1]=next[j]+1 */
if (k == -1 || p[j] == p[k]) {
++k;
++j;
/* if(p[j] != p[k]) */next[j] = k;
// else next[j] = next[k];
}
else k = next[k];
}
}
const int maxn = 400010;
char s[maxn];
int next[maxn];
stack<int> p;
int main()
{
while(scanf("%s",s) != EOF) {
GetNext(s,next);
int k = strlen(s);
while(next[k] > 0) {
p.push(next[k]);
k = next[k];
}
while(!p.empty()) {
printf("%d ",p.top());
p.pop();
}
printf("%d",strlen(s));
printf("\n");
}
return 0;
}
POJ2752 Seek the Name, Seek the Fame next数组应用
標簽：
原文地址：http://blog.csdn.net/area_52/article/details/43309315
