poj2752

poj2752
找所有的前缀等于后缀，那就是找所有前缀等于后缀的前缀，递归再用栈存一下

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cmath>

#include<ctime>

#include<set>

#include<map>

#include<stack>

#include<cstring>

#define inf 2147483647

#define ls rt<<1

#define rs rt<<1|1

#define lson ls,nl,mid,l,r

#define rson rs,mid+1,nr,l,r

#define N 400010

#define For(i,a,b) for(int i=a;i<=b;i++)

#define p(a) putchar(a)

#define g() getchar()

using namespace std;

int kmp[N];

int lb,k;

char b[N];

stack<int>s;

void in(int &x){

    int y=;

    char c=g();x=;

    while(c<''||c>''){

        if(c=='-')y=-;

        c=g();

    }

    while(c<=''&&c>=''){

        x=(x<<)+(x<<)+c-'';c=g();

    }

    x*=y;

}

void o(int x){

    if(x<){

        p('-');

        x=-x;

    }

    if(x>)o(x/);

    p(x%+'');

}

void clear(){

    k=;

    memset(kmp,,sizeof(kmp));

}

int main(){

    while(cin>>(b+)){

        clear();

        lb=strlen(b+);

        For(i,,lb){

            while(k&&b[i]!=b[k+])

                k=kmp[k];

            if(b[k+]==b[i])

                k++;

            kmp[i]=k;

        }

        k=lb;

        s.push(lb);

        while(kmp[k]>){

            s.push(kmp[k]);

            k=kmp[k];

        }

        while(!s.empty()){

            o(s.top());p(' ');

            s.pop();

        }

        p('\n');

    }

    return ;

}