<span>POJ - 1226 Substrings (后缀数组)</span>

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<cstring>
  7 using namespace std;
  8 
  9 //sa:字典序中排第i位的起始位置在str中第sa[i]  sa[1~n]为有效值
 10 
 11 //rnk:就是str第i个位置的后缀是在字典序排第几 rnk[0~n-1]为有效值
 12 
 13 //height：字典序排i和i-1的后缀的最长公共前缀  height[2~n]为有效值，第二个到最后一个
 14 
 15 const int INF=0x3f3f3f3f;
 16 const int maxn = 1e5+10;
 17 int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn];
 18 int rnk[maxn],height[maxn];
 19 char s[maxn];
 20 int r[maxn],n,L;
 21 int be[maxn],vis[110];
 22 
 23 int cmp(int *r,int a,int b,int k)
 24 {
 25     return r[a]==r[b]&&r[a+k]==r[b+k];
 26 }
 27 
 28 void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长
 29 {
 30     int i,j,p,*x=wa,*y=wb,*t;
 31     for(i=0; i<m; i++)  wsf[i]=0;
 32     for(i=0; i<=n; i++)  wsf[x[i]=r[i]]++;
 33     for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
 34     for(i=n; i>=0; i--)  sa[--wsf[x[i]]]=i;
 35     p=1;
 36     j=1;
 37     for(; p<=n; j*=2,m=p){
 38         for(p=0,i=n+1-j; i<=n; i++)  y[p++]=i;
 39         for(i=0; i<=n; i++)  if(sa[i]>=j)  y[p++]=sa[i]-j;
 40         for(i=0; i<=n; i++)  wv[i]=x[y[i]];
 41         for(i=0; i<m; i++)  wsf[i]=0;
 42         for(i=0; i<=n; i++)  wsf[wv[i]]++;
 43         for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
 44         for(i=n; i>=0; i--)  sa[--wsf[wv[i]]]=y[i];
 45         swap(x,y);
 46         x[sa[0]]=0;
 47         for(p=1,i=1; i<=n; i++)
 48             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
 49     }
 50 }
 51 
 52 void getheight(int *r,int n)//n为添加0后的总长
 53 {
 54     int i,j,k=0;
 55     for(i=1; i<=n; i++)  rnk[sa[i]]=i;
 56     for(i=0; i<n; i++){
 57         if(k)
 58             k--;
 59         else
 60             k=0;
 61         j=sa[rnk[i]-1];
 62         while(r[i+k]==r[j+k])
 63             k++;
 64         height[rnk[i]]=k;
 65     }
 66 }
 67 
 68 bool check(int k)
 69 {
 70     memset(vis,0,sizeof(vis));
 71     int cnt=0;
 72     for(int i=2;i<=L;i++){
 73         if(height[i]>=k){
 74             if(!vis[be[sa[i]]]) cnt++;
 75             vis[be[sa[i]]]=1;               //就是这个地方卡了我快3个小时！！！
 76             if(!vis[be[sa[i-1]]]) cnt++;
 77             vis[be[sa[i-1]]]=1;
 78         }
 79         else {
 80             memset(vis,0,sizeof(vis));
 81             cnt=0;
 82         }
 83         if(cnt>=n) return 1;
 84     }
 85     return 0;
 86 }
 87 
 88 int main()
 89 {
 90     ios::sync_with_stdio(false);
 91     cin.tie(0);
 92     cout.tie(0);
 93     int t;
 94     cin>>t;
 95     while(t--){
 96         cin>>n;
 97         L=0;
 98         for(int i=0;i<n;i++){
 99             cin>>s;
100             int len=strlen(s);
101             for(int j=0;j<len;j++){
102                 r[L]=s[j];
103                 be[L++]=i;
104             }
105             r[L]=i+200;
106             be[L++]=i;
107             for(int j=len-1;j>=0;j--){
108                 r[L]=s[j];
109                 be[L++]=i;
110             }
111             if(i!=n-1) r[L]=i+n+200,be[L++]=i;
112         }
113         if(n==1) {
114             cout<<strlen(s)<<endl;
115             continue;
116         }
117         r[L]=0;
118         getsa(r,sa,L,500);
119         getheight(r,L);
120         int l=0,r=105,ans=0;
121         while(l<=r){
122             int mid=l+r>>1;
123             if(check(mid)) ans=mid,l=mid+1;
124             else r=mid-1;
125         }
126         cout<<ans<<endl;
127     }
128     return 0;
129 }