FZU 1901

簡單KMP

[cpp]
#include<cstdio> 
#include<cstring> 
#include<vector> 
#include<algorithm> 
using namespace std; 
char s[1000005]; 
int next[1000005],flag,len; 
void getnext(){ 
    int k=1,j=0; 
    next[k]=0; 
    while(k<=len+1){ 
        if(j==0||s[k]==s[j]){ 
            ++j,++k; 
            next[k]=j; 
        } 
        else 
            j=next[j]; 
    } 
} 
int main(){ 
    int t,T,i; 
    vector<int>v; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%s",&s[1]); 
        len=strlen(&s[1]); 
        getnext(); 
        int tem=len; 
        v.clear(); 
        while(next[tem+1]>1){ 
            v.push_back(len+1-next[tem+1]); 
            tem=next[tem+1]-1; 
        } 
        v.push_back(len); 
        //sort(v.begin(),v.end()); 
        printf("Case #%d: %d\n",t,v.size()); 
        for(i=0;i<v.size();i++) 
            if(i==0) 
                printf("%d",v[i]); 
            else 
                printf(" %d",v[i]); 
        printf("\n"); 
    } 
}