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

显然可以通过后缀数组快速找到询问的两个串分别是什么，然后正反各建一个后缀数组来求两个串的LCP和LCS即可。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=,inf=1e9;

 char s[N];

 ll ans,x,y;

 int n,Q,lg[N];

 struct P{ int x,y; };

 struct SA{

     ll sm[N];

     char s[N];

     int x[N],y[N],c[N],sa[N],rk[N],h[N],mn[N][];

     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]; }

     void build(int m){

         rep(i,,m) c[i]=;

         rep(i,,n) c[x[i]=s[i]-'a'+]++;

         rep(i,,m) c[i]+=c[i-];

         for (int i=n; i; i--) sa[c[x[i]]--]=i;

         for (int k=,p=; p<n; k<<=,m=p){

             p=;

             rep(i,n-k+,n) y[++p]=i;

             rep(i,,n) if (sa[i]>k) y[++p]=sa[i]-k;

             rep(i,,m) c[i]=;

             rep(i,,n) c[x[y[i]]]++;

             rep(i,,m) c[i]+=c[i-];

             for (int i=n; i; i--) sa[c[x[y[i]]]--]=y[i];

             rep(i,,n) y[i]=x[i]; x[sa[p=]]=;

             rep(i,,n) x[sa[i]]=Cmp(sa[i],sa[i-],k) ? p : ++p;

         }

     }

     void init(){

         rep(i,,n) rk[sa[i]]=i;

         int k=;

         rep(i,,n){

             for (int j=sa[rk[i]-]; i+k<=n && j+k<=n && s[i+k]==s[j+k]; k++);

             h[rk[i]]=k; if (k) k--;

         }

         rep(i,,n) sm[i]=sm[i-]+n-sa[i]+-h[i],mn[i][]=h[i];

         rep(j,,) rep(i,,n-(<<j)+) mn[i][j]=min(mn[i][j-],mn[i+(<<(j-))][j-]);

     }

     int que(int l,int r){

         if (l==r) return inf;

         l++; int t=lg[r-l+]; return min(mn[l][t],mn[r-(<<t)+][t]);

     }

     P get(ll k){

         int L=,R=n; int ans1,ans2;

         if (sm[n]<k) return (P){-,-};

         while (L<=R){

             int mid=(L+R)>>;

             if (sm[mid]>=k) ans1=mid,ans2=n-sa[mid]+-(sm[mid]-k),R=mid-; else L=mid+;

         }

         return (P){ans1,ans2};

     }

 }S1,S2;

 int main(){

     freopen("bzoj3230.in","r",stdin);

     freopen("bzoj3230.out","w",stdout);

     scanf("%d%d%s",&n,&Q,s+);

     rep(i,,n) lg[i]=lg[i>>]+;

     rep(i,,n) S1.s[i]=S2.s[n-i+]=s[i];

     S1.build(); S2.build(); S1.init(); S2.init();

     rep(i,,Q){

         scanf("%lld%lld",&x,&y); ans=;

         if (S1.sm[n]<y){ puts("-1"); continue; }

         P xx=S1.get(x),yy=S1.get(y);

         ll k=min(S1.que(xx.x,yy.x),min(xx.y,yy.y)); ans+=k*k;

         xx.x=S2.rk[n-S1.sa[xx.x]+-xx.y]; yy.x=S2.rk[n-S1.sa[yy.x]+-yy.y];

         k=min(S2.que(min(xx.x,yy.x),max(xx.x,yy.x)),min(xx.y,yy.y)); ans+=k*k;

         printf("%lld\n",ans);

     }

     return ;

 }