BZOJ-3230: 相似子串（后缀数组+RMQ+二分查找）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3230

首先对原串和原串反过来的串做后缀数组，求出sa[],rank[],height[]，然后利用height[]查询最长公共前缀后缀，然后二分查找排名为i，j的子串位置，然后得出答案，记得long long。

代码：

09fa513d269759ee65948ccdb0fb43166c22dff4.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define MAXN 200100
#define inf 0x7fffffff
#define MAXB 21
 
char s0[MAXN],s1[MAXN];
int sa0[MAXN],rank0[MAXN],height0[MAXN],sa1[MAXN],rank1[MAXN],height1[MAXN];
int n,m;
 
int w[MAXN],r[MAXN],x[MAXN],y[MAXN];
 
void make_sa(char *s,int N,int *sa,int *rank,int *height) {
    s[0]=sa[0]=0;
    int Nn,b=1,M=N;
    for (int i=0;i++<N;) M=max(M,rank[i]=s[i]);
    do {
        for (int i=0;i++<N;) x[i]=rank[i],y[i]=i+b<=N?rank[i+b]:0;
        b<<=1;
        for (int i=0;i<=M;i++) w[i]=0;
        for (int i=0;i++<N;) w[y[i]]++;
        for (int i=0;i++<M;) w[i]+=w[i-1];
        for (int i=0;i++<N;) r[w[y[i]]--]=i;
        for (int i=0;i<=M;i++) w[i]=0;
        for (int i=0;i++<N;) w[x[r[i]]]++;
        for (int i=0;i++<M;) w[i]+=w[i-1];
        for (int i=N;i;i--) sa[w[x[r[i]]]--]=r[i];
        Nn=0;
        for (int i=0;i++<N;) {
            if (i==1||x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]) Nn++;
            rank[sa[i]]=Nn;
        }
    } while (Nn<N);
    int k=0;
    for (int i=0;i++<N;) {
        height[rank[i]]=k;
        for (int j=k;i+j<=N&&sa[rank[i]-1]+j<=N&&s[i+j]==s[sa[rank[i]-1]+j];j++) height[rank[i]]++;
        k=max(height[rank[i]]-1,0);
    }
}
 
long long suff[MAXN];
int st0[MAXN][MAXB],st1[MAXN][MAXB];
 
void Init_st() {
    int b=int(log2(n))+1;
    for (int i=0;i++<n;) st0[i][0]=height0[i],st1[i][0]=height1[i];
    for (int i=0;i++<b;) {
        for (int j=0;j++<n;) {
            st0[j][i]=min(st0[j][i-1],st0[j+(1<<(i-1))][i-1]);
            st1[j][i]=min(st1[j][i-1],st1[j+(1<<(i-1))][i-1]);
        }
    }
}
 
int Min(int l,int r,int u) {
    if (l>r) return 0x7fffffff;
    int k=int(log2(r-l+1));
    return u==0?min(st0[l][k],st0[r-(1<<k)+1][k]):min(st1[l][k],st1[r-(1<<k)+1][k]);
}
 
int Binary_Search(long long x) {
    int left=1,right=n;
    if (x<=suff[1]) return 1;
    if (x>suff[n-1]) return n;
    while (right-left>1) {
        int mid=(left+right)>>1;
        if (x>suff[mid]) left=mid
            ;  else right=mid;
    }
    return right;
}
 
long long MIN(long long a,long long b) {
    if (a<b) return a;
    return b;
}
 
int main() {
    scanf("%d%d",&n,&m);
    scanf("%s",s0);
    for (int i=n;i;i--) s0[i]=s0[i-1];
    for (int i=0;i++<n;) s1[i]=s0[n-i+1];
    make_sa(s0,n,sa0,rank0,height0);
    make_sa(s1,n,sa1,rank1,height1);
    suff[0]=0;
    for (int i=0;i++<n;) suff[i]=suff[i-1]+n-sa0[i]-height0[i]+1;
    Init_st();
    while (m--) {
        long long i,j;
        scanf("%lld%lld",&i,&j);
        if (i>j) swap(i,j);
        if (i>suff[n]||j>suff[n]) {
            printf("-1\n");
            continue;
        }
        int f0=Binary_Search(i),f1=Binary_Search(j);
        long long a,b,len0=height0[f0]+i-suff[f0-1],len1=height0[f1]+j-suff[f1-1];
        a=MIN(MIN(len0,len1),Min(f0+1,f1,0));
        long long c0=n-(sa0[f0]+len0-1)+1,c1=n-(sa0[f1]+len1-1)+1;
        int ll=min(rank1[c0],rank1[c1]),rr=max(rank1[c0],rank1[c1]);
        b=MIN(MIN(len0,len1),Min(ll+1,rr,1));
        long long ans=a*a+b*b;
        printf("%lld\n",ans);
    }
    return 0;
}