学步园

next数组的应用。。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int const MAXN = 400010;
char s[MAXN];
int next[MAXN],num[MAXN];
void Get_N(int l){
    memset(next,0,sizeof(next));
    for(int i = 1;i < l;i++){
        int j = next[i];
        while(j && s[i] != s[j]) j = next[j];
        if(s[i] == s[j]) next[i + 1] = j + 1;
        else next[i + 1] = 0;
    }
}
int main(){
    while(cin>>s){
        int l = strlen(s);
        Get_N(l);
        memset(num,0,sizeof(num));
        int k = next[l],cnt = 0;
        while(k){
            num[cnt++] = k;
            k = next[k];
        }
        for(int i = cnt - 1;i >= 0;i--){
            printf("%d ",num[i]);
        }
        printf("%d\n",l);
    }
    return 0;
}