后缀数组（入门）——51nod1732 51nod婚姻介绍所

题面：51nod1732
要死的SA！
今天入门后缀数组，具体的后缀数组教程网上也很多
这里推荐一个：传送门，讲的还不错
听说这题可以用hash直接过，不过的确是SA的入门题哦
这题要我们求的是串s对于x,y的最大公共前缀
掌握SA的基本操作之后这题的答案就是min(Height[rank[x]]~Height[rank[y]])
然后可以用线段树维护一下，还有读入输出优化，否则T了QAQ

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
using namespace std;
inline int read(){
    int k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    return k*f;
}
inline void write(int x){if(x>=10)write(x/10);putchar(x%10+'0');}
inline void writeln(int x){write(x);puts("");}
int n,m,rank[100001],sa[100001],a[100001],rank1[100001],h[100001];
int ton[100001],t[400001];
char s[100001];
inline void build(int l,int r,int nod){
    if(l==r){t[nod]=h[l];return;}
    int mid=l+r>>1;
    build(l,mid,nod*2);build(mid+1,r,nod*2+1);
    t[nod]=min(t[nod*2],t[nod*2+1]);
}
inline int ssum(int l,int r,int i,int j,int nod){
    if(l>=i&&r<=j)return t[nod];
    int mid=l+r>>1,ans=1e9;
    if(i<=mid)ans=min(ans,ssum(l,mid,i,j,nod*2));
    if(j>mid)ans=min(ans,ssum(mid+1,r,i,j,nod*2+1));
    return ans;
}
inline void Sort(){
    for(int i=0;i<=m;i++)ton[i]=0;
    for(int i=1;i<=n;i++)ton[rank[rank1[i]]]++;
    for(int i=1;i<=m;i++)ton[i]+=ton[i-1];
    for(int i=n;i;i--)sa[ton[rank[rank1[i]]]--]=rank1[i];
}
int main()
{
    n=read();scanf("%s",s+1);
    for(int i=1;i<=n;i++)a[i]=s[i];
    for(int i=1;i<=n;i++)rank[i]=a[i],rank1[i]=i;
    m=127;Sort();
    for(int i=1,j,p=1;p<n;i*=2,m=p){
        for(p=0,j=n-i+1;j<=n;j++)rank1[++p]=j;
        for(j=1;j<=n;j++)if(sa[j]>i)rank1[++p]=sa[j]-i;
        Sort();swap(rank,rank1);rank[sa[1]]=p=1;
        for(j=2;j<=n;j++)rank[sa[j]]=(rank1[sa[j]]==rank1[sa[j-1]]&&rank1[sa[j]+i]==rank1[sa[j-1]+i])?p:++p;
    }
    for(int i=1,j=0,k=0;i<=n;h[rank[i++]]=k)
        for(k=k?k-1:k,j=sa[rank[i]-1];a[i+k]==a[j+k];++k);
    build(1,n,1);
    int Q=read();
    while(Q--){
        int x=read()+1,y=read()+1;
        if(x==y){writeln(n-x+1);continue;}
        int xx=rank[x],yy=rank[y];
        if(xx>yy)swap(xx,yy);xx++;
        writeln(ssum(1,n,xx,yy,1));
    }
    return 0;
}