2752.cpp

这些是我到目前在PKU上做出的题目

#include <stdio.h>
#include <string.h>
void getNext(char* s,int length,int *next)
{
    int i=1,j=0;
    next[1]=0;
    while(i<=length+1&&j<=length)
    {
        if(j==0||s[i]==s[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
int main()
{
    int index,i,j;
    
    int length=0;
    char *s=new char[400001];
    while(scanf("%s",s+1)!=-1)
    {
        length=strlen(s)-1;
        int *next=new int[length];
        int *result=new int[length];
        getNext(s,length,next);
        j=length+1;
        index=0;
        while(j!=1)
        {
            result[++index]=j;
            j=next[j];
        }
        for(i=index;i>0;i--)
            printf("%d ",result[i]-1);
        printf("\n");
    }
    return 0;
}