POJ-2752 Seek the Name, Seek the Fame（KMP）

    给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。

next的简单运用，递归打印next的值就好

//Memory: 3656 KB		Time: 141 MS
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 400100
using namespace std;
char str[maxn];
int next[maxn];
int n;
void getnext()
{

    next[0]=-1;
    int i=0,j=-1;
    while(i<n){
        while(j>-1&&str[i]!=str[j])
            j=next[j];
        j++;
        i++;
        next[i]=j;
    }
}
void print(int x)
{
    if(next[x]>0){
        print(next[x]);
        printf("%d ",next[x]);
    }
}
int main()
{
    while(~scanf("%s",str)){
        n=strlen(str);
        getnext();
        print(n);
        printf("%d\n",n);
    }
    return 0;
}

POJ-2752 Seek the Name, Seek the Fame（KMP）

原文：http://blog.csdn.net/kalilili/article/details/43867925