1 #include "algorithm"  2 #include "cstdio"  3 #include "cstring"  4 using namespace std;  5 #define maxn 220020  6   7 int wa[maxn],wb[maxn],wv[maxn],ws[maxn];  8 int rank[maxn],height[maxn];  9 int r[maxn],sa[maxn],RMQ[maxn][20]; 10 char s[110010]; 11 int n; 12  13 int cmp(int *r,int a,int b,int l) 14 { 15     return r[a]==r[b]&&r[a+l]==r[b+l]; 16 } 17  18 void da(int *r,int *sa,int n,int m) 19 { 20     int i,j,p,*x=wa,*y=wb,*t; 21     for(i=0; i<m; i++) ws[i]=0;     //注意此处有个小问题：ws和iostream里面某地重名了.. 22     for(i=0; i<n; i++) ws[x[i]=r[i]]++; 23     for(i=1; i<m; i++) ws[i]+=ws[i-1]; 24     for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i; 25     for(j=1,p=1; p<n; j*=2,m=p) 26     { 27  28         for(p=0,i=n-j; i<n; i++) y[p++]=i; 29         for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; 30         for(i=0; i<n; i++) wv[i]=x[y[i]]; 31         for(i=0; i<m; i++) ws[i]=0; 32         for(i=0; i<n; i++) ws[wv[i]]++; 33         for(i=1; i<m; i++) ws[i]+=ws[i-1]; 34         for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i]; 35         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) 36             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 37     } 38     return; 39 } 40  41 void calheight(int *r,int *sa,int n) 42 { 43     int i,j,k=0; 44     for(i=1; i<=n; i++) rank[sa[i]]=i; 45     for(i=0; i<n; height[rank[i++]]=k) 46         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++); 47     return; 48 } 49  50 bool _same(int lx,int ly,int l1,int l2) 51 { 52     return (((lx<=l1-1) && (ly>=l1+1))||((ly<=l1-1) && (lx>=l1+1))); 53 } 54  55 void ST()        //初始化 56 { 57     memset(RMQ,1,sizeof(RMQ)); 58     for(int i=1;i<=n;i++) 59         RMQ[i][0]=height[i]; 60     for(int j=1;(1<<j)<=n;j++) 61         for(int i=1;i+(1<<j)-1<=n;i++) 62         RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]); 63 } 64  65 int Query(int L,int R)    //求a[L..R]区间的最值 66 { 67     int k=0; 68     while((1<<(k+1))<=R-L+1) k++; 69     int tb=min(RMQ[L][k],RMQ[R-(1<<k)+1][k]); 70     return tb; 71 } 72  73 int calc(int l,int r)       //求l开始后缀和r开始后缀的最长公共前缀 74 { 75     int tl=rank[l],tr=rank[r]; 76     if (tl>tr)      swap(tl,tr); 77     tl++; 78     int ans=Query(tl,tr);       //相当于RMQ问题 79 //  printf("calc:  %d %d -- %d %d == %d\n",l,r,tl,tr,ans); 80     return ans; 81 } 82  83 int _max(int a,int b,int c,int d) 84 { 85     int mx=a; 86     if (b>mx) mx=b; 87     if (c>mx) mx=c; 88     if (d>mx) mx=d; 89     return mx; 90 } 91  92 //da(r,sa,n+1,128); 93 //calheight(r,sa,n); 94 int main() 95 { 96     while(~scanf("%s",s)) 97     { 98         n=strlen(s); 99 100         for (int i=0; i<n; i++)101             r[i]=int(s[i])-int(‘a‘)+1;102 103         r[n]=100;104         for (int i=n-1; i>=0; i--)105             r[2*n-i]=int(s[i])-int(‘a‘)+1;106         r[2*n+1]=0;107         int n2=n;       n=2*n+1;108 109 //      for (int i=0; i<=n; i++)      printf("%d ",r[i]);110 //        printf("\n %d   %d\n",n,n2);111 112         da(r,sa,n+1,128);113         calheight(r,sa,n);114 115 //      for (int i=0; i<=n; i++)116 //          printf("%d  %d  %d\n",sa[i],height[i],rank[i]);117 //      printf("\n");118 119         ST();120         int ans=1;121         for (int i=1; i<=n2-2; i++)122         {123             int t1=calc(i,n-i)*2;124             int t2=calc(i+1,n-i)*2+1;125             int t3=calc(i+1,n-i-1)*2;126 //          printf("%d %d %d\n",t1,t2,t3);127             ans=_max(ans,t1,t2,t3);128         }129         printf("%d\n",ans);130     }131     return 0;132 }