后缀数组（SA）

读入一个长度为的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为到。。

这道题让我们高效的求出一个串的后缀数组。求出后缀数组后能够更高效地解决一些字符串问题。

如何给每一个串的后缀排序？

如果是只用暴力的排序方法，时间复杂度会达到，不可过。所以要优化一下算法，使用倍增 + 基数排序的算法来完成。

我们定义为后缀数组，就是排名为的后缀是哪一个后缀。类似的，也定义一个代表后缀的排名。

大体思路

首先，我们最直观的，感受如何使用倍增算法：

可以看到，第次操作，都相当于是取出了以这个地方为开头的前个字母。一直取直到每一个数都不一样然后排序就可以出结果了。

但是这样有一个缺点是没有任何一种数据结构可以在极小的空间复杂度下存储一百万位数字并且比较。所以肯定需要边取边排序：

然后现在就是要使用高效的算法对中间的 41,13,34,... 进行排序。由于只有两个关键字，所以可以使用基数排序。

请注意：基数排序及其之反常识。它先从第二关键字排序，然后再按照第一关键字排序。途中要使用桶。

详细步骤

那么我们可以得出后缀排序方法的一种：

定义数组为桶数组，含义为每一个位置对应的元素。先将所有字母预处理，得到第一批 SA 数组（就是图中的部分数组对应的数组）。
将数组按照两个不同的关键字：进行排序（其中为每一次的偏移量，为）。
排序后再次处理数组，并且统计数组的值域个数。若其，说明现在数组已经两两不同了。直接 break。否则回到步骤 2，并且使。

int x[N], y[N], cnt[N];
int sa[N], rk[N], height[N];
int n, m;
char s[N];
void Get_SA(){
    m = 127; // 所有字符的范围：0~127
    for(int i=1;i<=n;i++) cnt[x[i] = s[i]] ++;
    for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
    for(int i=n;i>=1;i--) sa[cnt[x[i]]] = i, cnt[x[i]] --;
    for(int k=1;k<=n;k<<= 1){ // delta
        // 第二关键字
        memset(cnt, 0, sizeof cnt);
        for(int i=1;i<=n;i++) y[i] = sa[i];
        for(int i=1;i<=n;i++) cnt[x[y[i]+k]] ++;
        for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
        for(int i=n;i>=1;i--) sa[cnt[x[y[i]+k]]] = y[i], cnt[x[y[i]+k]] --;
        // 第一关键字
        memset(cnt, 0, sizeof cnt);
        for(int i=1;i<=n;i++) y[i] = sa[i];
        for(int i=1;i<=n;i++) cnt[x[y[i]]] ++;
        for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
        for(int i=n;i>=1;i--) sa[cnt[x[y[i]]]] = y[i], cnt[x[y[i]]] --;
        // 然后再处理桶数组 x
        for(int i=1;i<=n;i++) y[i] = x[i];
        m = 0;
        for(int i=1;i<=n;i++){
            if(y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) x[sa[i]] = m;
            else x[sa[i]] = ++ m;
        }
        if(m == n) break;
    }
}

求 Height 数组

一些后缀数组的题有些时候也要附带着高度数组 height。

我们定义为和的 LCP（最长公共前缀）的长度。

那么，我们可以找出在原串里对应的是哪个：设当前从遍历到，这里的指的是原字符串下标。那么对应的就是。

而关于数组有一个定理：。意思就是，。

所以，我们就可以利用这个定理来求出 Height 数组：

void Get_Height(){
    for(int i=1;i<=n;i++) rk[sa[i]] = i;
    for(int i=1,k=0;i<=n;i++){
        if(rk[i] == 1) continue;
        if(k > 0) k --;
        int j = sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k] == s[j+k]) k ++;
        height[rk[i]] = k;
    }
}

由于最多只会减去次，相应的，最多只会加次，所以求 Height 数组的复杂度自然就是了。