BZOJ3230 相似子串【后缀数组】

题目分析：
容易想到sa排好序之后，子串排名就是前面的子串减去height数组。所以正着做一遍，倒着做一遍就行了。
代码：
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn = 252000;
  5 const int N = 100000;
  6 
  7 int n,q;
  8 char str[maxn];
  9 
 10 int sa[maxn],rk[maxn],X[maxn],Y[maxn];
 11 int height[maxn],h[maxn],RMQ[maxn][19];
 12 int len[maxn],st1[maxn],st2[maxn];
 13 long long stnum[maxn];
 14 
 15 int chk(int x,int k){
 16     return rk[sa[x]]==rk[sa[x-1]]&&rk[sa[x]+(1<<k)]==rk[sa[x-1]+(1<<k)];
 17 }
 18 
 19 void getsa(){
 20     for(int i=0;i<n;i++) X[str[i]]++;
 21     for(int i=1;i<=N;i++) X[i] += X[i-1];
 22     for(int i=n-1;i>=0;i--) sa[X[str[i]]--] = i;
 23     for(int i = 2, num = 1;i <= n;i++)
 24     rk[sa[i]] = (str[sa[i]] == str[sa[i-1]]?num:++num);
 25     rk[sa[1]] = 1;
 26     for(int k=1;(1<<k-1)<=n;k++){
 27     for(int i=1;i<=N;i++) X[i] = 0;
 28     for(int i=n-(1<<k-1);i<n;i++) Y[i-n+(1<<k-1)+1]=i;
 29     for(int i=1,j=(1<<k-1)+1;i<=n;i++)
 30         if(sa[i]>=(1<<k-1))Y[j++]=sa[i]-(1<<k-1);
 31     for(int i=0;i<n;i++) X[rk[i]]++;
 32     for(int i=1;i<=N;i++) X[i]+=X[i-1];
 33     for(int i=n;i>=1;i--) sa[X[rk[Y[i]]]--] = Y[i];
 34     int num = 1; Y[sa[1]] = 1;
 35     for(int i=2;i<=n;i++) Y[sa[i]] = (chk(i,k-1)?num:++num);
 36     for(int i=0;i<n;i++) rk[i] = Y[i];
 37     if(num == n) break;
 38     }
 39 }
 40 
 41 void getheight(){
 42     for(int i=0;i<n;i++){
 43     if(i) h[i] = max(0,h[i-1]-1); else h[i] = 0;
 44     if(rk[i] == 1) continue;
 45     int comp = sa[rk[i]-1];
 46     while(str[comp+h[i]] == str[i+h[i]])h[i]++;
 47     }
 48     for(int i=0;i<n;i++) height[rk[i]] = h[i];
 49     for(int i=1;i<=n;i++) RMQ[i][0] = height[i];
 50     for(int k=1;(1<<k)<=n;k++){
 51     for(int i=1;i<=n;i++){
 52         if(i+(1<<k-1)>n) RMQ[i][k] = RMQ[i][k-1];
 53         else RMQ[i][k] = min(RMQ[i][k-1],RMQ[i+(1<<k-1)][k-1]);
 54     }
 55     }
 56 }
 57 
 58 int getLCP(int L,int R){
 59     if(L > R) swap(L,R);
 60     if(L == R) return n-sa[L];
 61     L++;
 62     int k = 0; while((1<<k+1)<=R-L+1)k++;
 63     return min(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
 64 }
 65 
 66 void read(){
 67     scanf("%d%d",&n,&q);
 68     scanf("%s",str);
 69 }
 70 
 71 long long ans[maxn];
 72 void work(){
 73     getsa();
 74     getheight();
 75     for(int i=1;i<=n;i++) stnum[i] = stnum[i-1]+(n-sa[i])-height[i];
 76     for(int i=1;i<=q;i++){
 77     long long u,v; scanf("%lld%lld",&u,&v);
 78     if(u > v) swap(u,v); if(v > stnum[n]){ans[i] = -1;continue;}
 79     int pn = lower_bound(stnum+1,stnum+n+1,u)-stnum;
 80     int pm = lower_bound(stnum+1,stnum+n+1,v)-stnum;
 81     len[i] = min(height[pn]+u-stnum[pn-1],height[pm]+v-stnum[pm-1]);
 82     st1[i] = n-(sa[pn]+height[pn]+u-stnum[pn-1]);
 83     st2[i] = n-(sa[pm]+height[pm]+v-stnum[pm-1]);
 84     int LCP = getLCP(pn,pm); LCP = min(LCP,len[i]);
 85     ans[i]+=1ll*LCP*LCP;
 86     }
 87     for(int i=0;i<n/2;i++) swap(str[i],str[n-i-1]);
 88     memset(sa,0,sizeof(sa));
 89     memset(rk,0,sizeof(rk));
 90     memset(X,0,sizeof(X));
 91     memset(Y,0,sizeof(Y));
 92     memset(height,0,sizeof(height));
 93     memset(h,0,sizeof(h));
 94     memset(RMQ,0,sizeof(RMQ));
 95     getsa();
 96     getheight();
 97     for(int i=1;i<=q;i++){
 98     if(ans[i] == -1) continue;
 99     int LCP = getLCP(rk[st1[i]],rk[st2[i]]); LCP = min(LCP,len[i]);
100     ans[i] += 1ll*LCP*LCP;
101     }
102     for(int i=1;i<=q;i++) printf("%lld
",ans[i]);
103 }
104 
105 int main(){
106     read();
107     work();
108     return 0;
109 }
BZOJ3230 相似子串 【后缀数组】

BZOJ3230 相似子串【后缀数组】
