POJ2752 Seek the Name, Seek the Fame

Description

Input

Output

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5

题意：找一个字符串中所有前缀和后缀相同的子串

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

char s[1000009];
int nt[1000009];
int len;

void getnext()
{
    int k=-1,j=0;
    nt[0]=-1;

    while(j<len)
    {
        if(k<0 || s[j]==s[k])
        {
            j++;
            k++;
            nt[j]=k;
        }
        else
            k=nt[k];
    }
}

int ans[400009];

int main()
{
    while(~scanf("%s",s))
    {
        len=strlen(s);
        getnext();

        for(int i=0;i<=len;i++)
            cout<<nt[i]<<" ";
            cout<<endl;

        int cnt=0;
        ans[0]=len;
        for(int i=nt[len];i>0;i=nt[i])//next数组的性质。
            ans[++cnt]=i;

        for(int i=cnt;i>0;i--)
            cout<<ans[i]<<" ";
        cout<<ans[0]<<endl;

    }
    return 0;
}

POJ2752 Seek the Name, Seek the Fame

原文：http://blog.csdn.net/wust_zjx/article/details/47449083