poj 2752 Seek the Name, Seek the Fame

前のブログではnextがループセクションを求めることができることがわかり、この問題は接頭辞と接尾辞が同じであることを探しています.まず自分自身が答えに違いない.そして、nextには現在接頭辞と一致している桁数が格納されているので、nextを直接再帰的に出力すればよい.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char a[400010];
int next[400010];
void print(int who)
{
    if(next[who]==0)
    {
        return ;
    }
    print(next[who]);
    cout<<next[who]<<" ";
}
int main()
{
    while(scanf("%s",a)==1)
    {
        int len=strlen(a);
        next[0]=-1;
        int i=0;
        int j=next[0];
        while(i<len)
        {
            if(j==-1||a[i]==a[j])
            {
                i++;
                j++;
                next[i]=j;
            }
            else
            {
                j=next[j];
            }
        }
        print(len);
        cout<<len<<endl;
    }
    return 0;
}