后缀数组

解析日后补上

模板

$$\begin{aligned} s[0\dots n-1]&\text{:字符串}\\sa[1\dots n]&\text{:字典序第i小的是哪个后缀}\\rank[0\dots n-1]&\text{:后缀i的排名}\\height[i]&\text{:}lcp(sa[i], sa[i-1]) \end{aligned}$$

const int N = 1e5 + 1e4;
struct suffix_array{ // 后缀数组模板
    int n,rank[N*2],sa[N*2],height[N*2],tmp[N*2],cnt[N*2];
    char s[N];
    void suffixArray(int n, int m){
        int i, j, k; n++;
        for(i=0; i<n*2+5; i++) rank[i]=sa[i]=height[i]=tmp[i]=0;
        for(i=0;i<m;i++) cnt[i]=0;
        for(i=0;i<n;i++) cnt[rank[i]=s[i]]++; // 预处理需要在外面进行
        for(i=1;i<m;i++) cnt[i]+=cnt[i-1];
        for(i=0;i<n;i++) sa[--cnt[rank[i]]]=i;
        for(k=1;k<=n;k<<=1){
            for(i=0;i<n;i++){
                j = sa[i] - k;
                if(j<0) j+=n;
                tmp[cnt[rank[j]]++] = j;
            }
            sa[tmp[cnt[0]=0]]=j=0;
            for(i=1;i<n;i++){
                if(rank[tmp[i]]!=rank[tmp[i-1]] || 
                rank[tmp[i]+k] != rank[tmp[i-1]+k]) cnt[++j]=i;
                sa[tmp[i]] = j; // 相当于rank[sa[i]] = j;
            }
            memcpy(rank, sa, n*sizeof(int));
            memcpy(sa, tmp, n*sizeof(int));
            if(j>=n-1) break;
        }
        for(j=rank[height[i=k=0]=0];i<n-1;i++,k++)
            while(~k&&s[i]!=s[sa[j-1]+k]) height[j]=k--, j=rank[sa[j]+1];
    }
}SA; // 模板

struct RMQ{
    int best[20][N], n;
    void build(int nx){
        n = nx;
        // 不需要特别处理best[0][1]
        for(int i=2; i<=n; i++) best[0][i] = SA.height[i];
        for(int step=1; (1<<step)<=n; step++){
            for(int i=1; i+(1<<step)-1<=n; i++)
                best[step][i] = min(best[step-1][i], best[step-1][i+(1<<(step-1))]);
        }
    }
    int query(int a, int b){
        a = SA.rank[a], b = SA.rank[b];
        if(a > b) swap(a, b);
        a += 1; // [best[x][1] for x in range(0, inf)]永远不会被访问
        int p = log2(b - a + 1);
        return min(best[p][a], best[p][b-(1<<p)+1]);
    }
}rmq;