@[toc]

后缀数组 Height

利用后缀数组快速求出2个后缀的lcp长度
lcp:最长公共前缀
lcp(suf(i),suf(j))
记Height[l] = 排名第(l-1)后缀和排名第l后缀的lcp长度
Height[l] = lcp(suf(SA[l-1]),suf(SA[l]))

l = 后缀suf(i)的排名
r = 后缀suf(j)的排名
结论：
lcp(suf(i),suf(j)) = min(Height[l+1]...Height[r] )
即两个后缀的lcp = 它们排名区间中Height的最小值
维护rmq

求Height数组

暴力求O(N^2^)

for i =1-N
     l =rank[i]
    j = sa[l-i]
    k=0
    while(s[i+k]==s[j+k])k++;
    Height[l]=k;

suf(k)为s(k…n)构成的子串
SA[1]排序第1的后缀的开始位置
令l =rank[i],r = rank[i-1]
Height[l] = lcp(suf(SA[l-i],suf(i)))
Height[r] = lcp(suf(SA[r-1],suf(i-1)))
结论：
Height[l] >= Height[r]-1
Height[rank[i]] >= Height[rank[i-1]] - 1

利用Height[rank[i]] >= Height[rank[i-1]] - 1优化暴力
复杂度为O(N)

for i =1-N
    j = sa[l-i]
    k=max(0,Height[rank[i-1]-1])
    while(s[i+k]==s[j+k])k++;
    Height[l]=k;

之后再用st表来来维护Height的rmq信息

总结：

倍增求长度为2^k^子串的字典序
排序是二元组的基数排序
求SA O(NlogN)
求Height O(N)
求lcp
st表 预处理O(NogN)+单次询问O(1)
P3809 【模板】后缀排序
P4051 【JSOI2007】字符加密

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN =1000005;

char ch[MAXN], all[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m; 
char str[MAXN];
//rk[i] 第i个后缀的排名; sa[i] 排名为i的后缀位置; height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
//tax[i] 计数排序辅助数组; tp[i] rk的辅助数组(计数排序中的第二关键字),与sa意义一样。
//a为原串
void RSort() {
    //rk第一关键字,tp第二关键字。
    for (int i = 0; i <= m; i ++) tax[i] = 0;
    for (int i = 1; i <= n; i ++) tax[rk[tp[i]]] ++;
    for (int i = 1; i <= m; i ++) tax[i] += tax[i-1];
    for (int i = n; i >= 1; i --) sa[tax[rk[tp[i]]] --] = tp[i]; //确保满足第一关键字的同时，再满足第二关键字的要求
} //计数排序,把新的二元组排序。

int cmp(int *f, int x, int y, int w) { return f[x] == f[y] && f[x + w] == f[y + w]; } 
//通过二元组两个下标的比较，确定两个子串是否相同

void Suffix() {
    //sa
    for (int i = 1; i <= n; i ++) rk[i] = a[i], tp[i] = i;
    m = 127 ,RSort(); //一开始是以单个字符为单位，所以(m = 127)

    for (int w = 1, p = 1, i; p < n; w += w, m = p) { //把子串长度翻倍,更新rk

        //w 当前一个子串的长度; m 当前离散后的排名种类数
        //当前的tp(第二关键字)可直接由上一次的sa的得到
        for (p = 0, i = n - w + 1; i <= n; i ++) tp[++ p] = i; //长度越界,第二关键字为0
        for (i = 1; i <= n; i ++) if (sa[i] > w) tp[++ p] = sa[i] - w;

        //更新sa值,并用tp暂时存下上一轮的rk(用于cmp比较)
        RSort(), swap(rk, tp), rk[sa[1]] = p = 1;

        //用已经完成的sa来更新与它互逆的rk,并离散rk
        for (i = 2; i <= n; i ++) rk[sa[i]] = cmp(tp, sa[i], sa[i - 1], w) ? p : ++ p;
    }
    //离散：把相等的字符串的rk设为相同。
    //LCP
    int j, k = 0;
    for(int i = 1; i <= n; height[rk[i ++]] = k) 
        for( k = k ? k - 1 : k, j = sa[rk[i] - 1]; a[i + k] == a[j + k]; ++ k);
    //这个知道原理后就比较好理解程序
}

void Init() {
    scanf("%s", str);
    n = strlen(str);
    for (int i = 0; i < n; i ++) a[i + 1] = str[i];
}

int main() {
    Init();
    Suffix();

    int ans = height[2];
    for (int i = 3; i <= n; i ++) ans += max(height[i] - height[i - 1], 0);
    for(int i=1;i<=n;i++)
   cout<<sa[i]<<" ";
   puts("");
//    printf("%d\n", ans);    
}