1 #include<cstdio>  2 #include<cstdlib>  3 #include<cstring>  4 #include<iostream>  5 #include<queue>  6 using namespace std;  7   8 const int N=2*100010;  9 int sl,cl,tot,last,step[N],pre[N],son[N][30],in[N],r[N],c[N],ans[N]; 10 bool vis[N]; 11 char s[N]; 12 queue<int> Q; 13  14 int maxx(int x,int y){return x>y ? x:y;} 15  16 int add_node(int x) 17 { 18     step[++tot]=x; 19     return tot; 20 } 21  22 void clear() 23 { 24     memset(step,0,sizeof(step)); 25     memset(pre,0,sizeof(pre)); 26     memset(son,0,sizeof(son)); 27     memset(in,0,sizeof(in)); 28     memset(r,0,sizeof(r)); 29     tot=0;add_node(0);last=1; 30 } 31  32 void extend(int ch) 33 { 34     int p=last,np=add_node(step[p]+1); 35     while(p && !son[p][ch]) 36     { 37         son[p][ch]=np; 38         in[np]++; 39         p=pre[p]; 40     } 41     if(!p) pre[np]=1; 42     else 43     { 44         int q=son[p][ch]; 45         if(step[q]==step[p]+1) pre[np]=q; 46         else 47         { 48             int nq=add_node(step[p]+1); 49             for(int i=1;i<=26;i++)  50                 if(son[q][i]) son[nq][i]=son[q][i],in[son[q][i]]++; 51             pre[nq]=pre[q]; 52             pre[np]=pre[q]=nq; 53             while(p && son[p][ch]==q) in[q]--,in[nq]++,son[p][ch]=nq,p=pre[p]; 54         } 55     } 56     last=np; 57 } 58  59 void get_tp() 60 { 61     while(!Q.empty()) Q.pop(); 62     memset(vis,0,sizeof(vis)); 63     Q.push(1);vis[1]=1;cl=0; 64     while(!Q.empty())  65     { 66         int x=Q.front();c[++cl]=x;vis[x]=0;Q.pop(); 67         for(int i=1;i<=26;i++) 68         { 69             int y=son[x][i]; 70             if(!y) continue; 71             in[y]--; 72             if(!in[y] && !vis[y]) vis[y]=1,Q.push(y); 73         } 74     } 75 } 76  77 void get_right() 78 { 79     int x=1,ch; 80     for(int i=1;i<=sl;i++) 81     { 82         ch=s[i]-‘A‘+1; 83         x=son[x][ch]; 84         r[x]++; 85     } 86     for(int i=cl;i>=1;i--) r[pre[c[i]]]+=r[c[i]]; 87 } 88  89 void output(int x) 90 { 91     printf("x = %d  pre = %d  r = %d\n",x,pre[x],r[x]); 92     for(int i=1;i<=26;i++) 93     { 94         if(son[x][i]) printf("son %d = %d\n",i,son[x][i]); 95     } 96     printf("\n"); 97 } 98  99 int main()100 {101     freopen("a.in","r",stdin);102     // freopen("a.out","w",stdout);103     int cas=0;104     while(1)105     {106         gets(s+1);107         sl=strlen(s+1);108         int l=0;109         for(int i=1;i<=sl;i++) 110             if(s[i]>=‘A‘ && s[i]<=‘Z‘) s[++l]=s[i];111         sl=l;112         if(sl==0) return 0;113 114         clear();115         for(int i=1;i<=sl;i++) extend(s[i]-‘A‘+1);116         get_tp();117         get_right();118         memset(ans,0,sizeof(ans));119         for(int i=1;i<=tot;i++) ans[step[i]]=maxx(ans[step[i]],r[i]);120 121         for(int i=1;i<sl;i++) ans[i]=maxx(ans[i],ans[i+1]);122         123         for(int i=1;i<=sl;i++) 124         {125             if(ans[i]<2) break;126             printf("%d\n",ans[i]);127         }128         printf("\n");129     }130     return 0;131 }