1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6 typedef long long LL; 7  8 const int maxn = 1e5+100; 9 int wa[maxn],wb[maxn],wv[maxn],ws[maxn];10 int sa[maxn],r[maxn];11 int rank[maxn],height[maxn];12 char s[maxn];13 int cmp(int *r,int a,int b,int l){14     return r[a]==r[b]&&r[a+l]==r[b+l];15 }16 17 void da(int *r,int *sa,int n,int m){18     int i,j,p,*x=wa,*y=wb,*t;19     for(i=0;i<m;i++) ws[i] = 0;20     for(i=0;i<n;i++) ws[x[i]=r[i]]++;21     for(i=1;i<m;i++) ws[i]+= ws[i-1];22     for(i=n-1;i>=0;i--) sa[--ws[x[i]]] = i;23     for(j=1,p=1;p<n;j*=2,m=p){24         for(p=0,i=n-j;i<n;i++) y[p++] = i;25         for(i=0;i<n;i++) if(sa[i]>=j) y[p++] = sa[i]-j;26         for(i=0;i<n;i++) wv[i] = x[y[i]];27         for(i=0;i<m;i++) ws[i] = 0;28         for(i=0;i<n;i++) ws[wv[i]]++;29         for(i=1;i<m;i++) ws[i]+=ws[i-1];30         for(i=n-1;i>=0;i--) sa[--ws[wv[i]]] = y[i];31         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)32             x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;33     }34 }35 36 void calheight(int *r,int *sa,int n){37     int i,j,k=0;38     for(i=1;i<=n;i++) rank[sa[i]]=i;39     for(i=0;i<n;height[rank[i++]]=k)40         for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);41 }42 43 int main(){44     gets(s);45     int len = strlen(s);46     for(int i=0;i<len;i++){47         r[i] = s[i] - ‘a‘ + 1;48     }49     da(r,sa,len+1,100);50     calheight(r,sa,len);51 //    for(int i=1;i<=len;i++){52 //        printf("%d ",sa[i]);53 //    }54 //    puts("");55 //    for(int i=2;i<=len;i++) printf("%d ",height[i]); puts("");56     int ans = 0;57     for(int k=1;k<=len;k++){58         int maxn = sa[1] , minn = sa[1];59         int q = 0;60 //        printf("now k=%d\n",k);61         for(int i=2;i<=len+1;i++){62             if( height[i]<k||i==len+1 ){63                 if( maxn-minn>=k ) ans++;64                 maxn = minn = sa[i];65 //                printf("i=%d sa[i]=%d maxn = %d minn = %d\n",i,sa[i],maxn,minn);66             } else if(i<=len){67                 maxn = max(sa[i],maxn);68                 minn = min(sa[i],minn);69             }70         }71 //        printf("k=%d q=%d\n",k,q);72 //        q = 0;73     }74     printf("%d\n",ans);75     return 0;76 }