[BZOJ3230]相似子串(后缀数组)

显然可以通过后缀数组快速找到询问的两个串分别是什么，然后正反各建一个后缀数组来求两个串的LCP和LCS即可。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=100010,inf=1e9;
 9 char s[N];
10 ll ans,x,y;
11 int n,Q,lg[N];
12 struct P{ int x,y; };
13 
14 struct SA{
15     ll sm[N];
16     char s[N];
17     int x[N],y[N],c[N],sa[N],rk[N],h[N],mn[N][20];
18     
19     bool Cmp(int a,int b,int l){ return a+l<=n && b+l<=n && y[a]==y[b] && y[a+l]==y[b+l]; }
20     
21     void build(int m){
22         rep(i,0,m) c[i]=0;
23         rep(i,1,n) c[x[i]=s[i]-'a'+1]++;
24         rep(i,1,m) c[i]+=c[i-1];
25         for (int i=n; i; i--) sa[c[x[i]]--]=i;
26         for (int k=1,p=0; p<n; k<<=1,m=p){
27             p=0;
28             rep(i,n-k+1,n) y[++p]=i;
29             rep(i,1,n) if (sa[i]>k) y[++p]=sa[i]-k;
30             rep(i,0,m) c[i]=0;
31             rep(i,1,n) c[x[y[i]]]++;
32             rep(i,1,m) c[i]+=c[i-1];
33             for (int i=n; i; i--) sa[c[x[y[i]]]--]=y[i];
34             rep(i,1,n) y[i]=x[i]; x[sa[p=1]]=1;
35             rep(i,2,n) x[sa[i]]=Cmp(sa[i],sa[i-1],k) ? p : ++p;
36         }
37     }
38     
39     void init(){
40         rep(i,1,n) rk[sa[i]]=i;
41         int k=0;
42         rep(i,1,n){
43             for (int j=sa[rk[i]-1]; i+k<=n && j+k<=n && s[i+k]==s[j+k]; k++);
44             h[rk[i]]=k; if (k) k--;
45         }
46         rep(i,1,n) sm[i]=sm[i-1]+n-sa[i]+1-h[i],mn[i][0]=h[i];
47         rep(j,1,18) rep(i,1,n-(1<<j)+1) mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
48     }
49     
50     int que(int l,int r){
51         if (l==r) return inf;
52         l++; int t=lg[r-l+1]; return min(mn[l][t],mn[r-(1<<t)+1][t]);
53     }
54     
55     P get(ll k){
56         int L=1,R=n; int ans1,ans2;
57         if (sm[n]<k) return (P){-1,-1};
58         while (L<=R){
59             int mid=(L+R)>>1;
60             if (sm[mid]>=k) ans1=mid,ans2=n-sa[mid]+1-(sm[mid]-k),R=mid-1; else L=mid+1;
61         }
62         return (P){ans1,ans2};
63     }
64 }S1,S2;
65 
66 int main(){
67     freopen("bzoj3230.in","r",stdin);
68     freopen("bzoj3230.out","w",stdout);
69     scanf("%d%d%s",&n,&Q,s+1);
70     rep(i,2,n) lg[i]=lg[i>>1]+1;
71     rep(i,1,n) S1.s[i]=S2.s[n-i+1]=s[i];
72     S1.build(30); S2.build(30); S1.init(); S2.init();
73     rep(i,1,Q){
74         scanf("%lld%lld",&x,&y); ans=0;
75         if (S1.sm[n]<y){ puts("-1"); continue; }
76         P xx=S1.get(x),yy=S1.get(y);
77         ll k=min(S1.que(xx.x,yy.x),min(xx.y,yy.y)); ans+=k*k;
78         xx.x=S2.rk[n-S1.sa[xx.x]+2-xx.y]; yy.x=S2.rk[n-S1.sa[yy.x]+2-yy.y];
79         k=min(S2.que(min(xx.x,yy.x),max(xx.x,yy.x)),min(xx.y,yy.y)); ans+=k*k;
80         printf("%lld
",ans);
81     }
82     return 0;
83 }