后缀数组

参考:

以洛谷P3809 【模板】后缀排序为例，看了两天才理解了七成的数据结构┭┮﹏┭┮。

先上经典图

后缀数组是一个搞出字符串所有后缀的一个字典序排名。字典序就不解释了，不懂字典序你也不会来搜后缀数组了。。。然后

SA【】数组，是一个排行榜，SA[i] 表示排名i的后缀的开始位置。

rank【】是排名，rank【i】记录的是位置i的后缀字符串的排名

x【】y【】分别是关键字，buc【】是基数排序的桶，基数排序不是桶排，但是有共同点

SA和rank是一个逆运算。这点很重要rank[SA[i]] == i, SA[rank[i]] == i;

先第一步，先不管代码，弄懂上面那张图。aabaaaab按照大小关系离散化成11211112。

离散化：在比较10，500，90000的大小的时候，有的时候我们操作这么大的数不方便，比如数组标记的时候

把数据等价为1,2。就像上面的两位数合并后，计算rank再合并1

两两合并，这样就有了所有后缀前两个字母的排名，再次合并就有了前四个字母的排名，后面不够补0，这样补影响答案。最后不断倍增就获得了整个后缀的排名。

比如

    a  a  b  a  a  a  b
    1  1  2  1  1  1  2     这是单个字符的排名
    11 12 21 11 11 12 20    每个位置和后面跳【一】个位置合并，再离散化排名
    1   2  4  1  1  2  3     现在每个位置和后面跳【二】个位置合并
    14 21 41 11 12 13 20 30  这样在求排名就是每个位置长度为4的后缀的排名，不断倍增就能得出答案
                           这里应该对照上图以前看。
                           不断合并知道rank都不同。因为所以位置的后缀长度必定是不同的，所以字符串不可能相等

然后是代码，注释写代码里面了

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 7;

int n, m, len, SA[maxn], rnk[maxn], buc[maxn], x[maxn], y[maxn];

char str[maxn];

/**
后缀数组的构建
*/

void build() {
    m = 150;    ///边界，我们字符串是ASCII初始127，稍微大一点没影响。

    ///基数排序,首先清空桶
    for(int i = 0; i < m; i ++ ) { buc[i] = 0; }
    ///开始对数字每一个字符，即还未倍增的状态进行标记，存到x数组备用
    for(int i = 0; i < n; i ++ ) { buc[ x[i] = str[i] ] ++; }
    ///前缀和，这样后面能方便获得排名
    for(int i = 1; i < m; i ++ ) { buc[i] += buc[i - 1]; }
    ///计算SA值，SA[i]表示排名i的字符下标，这里还未倍增所以是单个字符的排名。
    ///遍历每个x[i],就是遍历数组的每个字符，在桶里的位置，前缀和后 buc[] 就是排名
    for(int i = 0; i < n; i ++ ) { SA[ --buc[ x[i] ] ] = i; }
    ///然后开始倍增了
    for(int k = 1; k <= n; k <<= 1) {
        int p = 0;

        ///难点1：这部分的对第二关键字(个位)基数排序
        ///y数组存的是第二关键字对应第一关键字的下标, y[0] = i 表示排名0的第二关键字的第一关键字位置，他们跨越了一个k的距离
        ///n-k 到 n-1 这部分没有第二关键字，就是经典图中的0，所以排名先放进y
        for(int i = n - k; i < n; i ++ ) { y[p++] = i; }
        ///SA[i]表示排名i的字符串在哪,数值表示的是下标,SA[i]>=k表示字符串开始位置在k以后
        ///这些【位置】是第二关键字，SA[i] - k就是找这些跨越长度k的对应的第一关键字的位置。不满足整个条件也没有对应的第一关键字
        ///想一想，我们不断倍增，基数排序，答案都是记在每一个后缀的起点位置的，这正是我们的目的所在
        ///下面这个循环0~n-1不能变，因为SA已经排好，按第一关键字的排序取第二关键字，
        ///因此y[i]才是排名，排名小的越前面。
        for(int i = 0; i < n; i ++ ) { if(SA[i] >= k) y[p++] = SA[i] - k; }

        ///接下来这一块是对第一关键字（十位）排名的计算
        ///清空桶
        for(int i = 0; i < m; i ++ ) { buc[i] = 0; }
        ///x[ y[i] ] 是第一关键字的...离散化后的映射值把，这个词了比较形象，第一次是字符，后面是那个排名
        ///表示大小的数值，比如aba排完121，不断倍增在不断离散出新的排名。
        for(int i = 0; i < n; i ++ ) { buc[ x[ y[i] ] ]++; }    ///
        for(int i = 1; i < m; i ++ ) { buc[i] += buc[i - 1]; }
        for(int i = n - 1; i >= 0; i -- ) { SA[ --buc[ x[ y[i] ] ] ] = y[i]; }
        ///在交换前y已经没用，交互后原来的y是x变成有用的了，x是没用的y，拿来存新的排名，所以下面动的是x[]
        swap(x, y);
        p = 1; x[ SA[0] ] = 0; ///最开始的排名，是为了防止下面-1的越界
        ///下面把字符串相同的变为排名相等，
        for(int i = 1; i < n; i ++ ) {
            if(y[ SA[i - 1] ] == y[ SA[i] ] && y[ SA[i - 1] + k] == y[ SA[i] + k]) {
                x[ SA[i] ] = p - 1;
            } else {
                x[ SA[i] ] = p ++;
            }
        }
        ///所有rnk都不同了，就不用倍增了
        if(p >= n) { break; }
        m = p;
    }
    for(int i = 0; i < n; i ++) { rnk[ SA[i] ] = i; }
}

int main()
{
    scanf("%s", str);
    n = strlen(str);
    build();
    for(int i = 0; i < n; i ++ ) {
        printf("%d%c", SA[i] + 1, " \n"[i == n - 1]);
    }
    return 0;
}

后缀数组记录

后缀数组