POJ 2752-Seek the Name, Seek the Fame(KMP的next数组运用)

poj 2752

Seek the Name, Seek the Fame

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 8261		Accepted: 3883

Description

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm: 

Step1. Connect the father's name and the mother's name, to a new string S. 
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S). 

Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

Input

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above. 

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

Output

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5

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

思路:

     巧妙的运用next数组,next数组中,next[i]表示的是长度为i的子串中最长的相同前后缀的长度,next[n]表示的就是主串的最长相同前后缀的长度,那么在主串中,(0~next[n])--A与((n-next[n])~n)--B应该是相同的字符串,为了方便叙述,称之为A串与B串,由前面可知要求既是主串的前缀又是后缀的子串,那么此时就要找A的前缀与B的后缀,有因为A,B是相同的字符串所以我们只需要看A就行了,说的不是很清楚,详细看这篇博客:http://www.cnblogs.com/dongsheng/archive/2012/08/13/2636261.html

代码如下:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int N=400005;
int next[N];
char str[N];
int ans[N];
void Getnext()
{
    int j=-1;
    int i=0;
    int len=strlen(str);
    next[0]=-1;
    while(i<len)
    {
        if(j==-1||str[i]==str[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
}
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        Getnext();
        int m=0;
        int len=strlen(str);
        int k=len;
        while(k>0)
        {
            ans[m]=k;
            m++;
            k=next[k];
        }
        for(int i=m-1;i>=0;i--)
        {
            cout<<ans[i]<<endl;
        }
    }
}