后缀数组学习笔记

都到现在了还不会后缀数组怕不是要凉

赶快学习一发

准确地说这个东西学了很多遍？

思想我觉得我大概是懂的，就是要求一个字符串的每个后缀的排名，我们使用基数排序，每一轮得到每个位置开始长度为 \(2^{\text{轮数}}\) 的子串的排名，然后类似于一个两位数之间的基数排序，这里两位数每一位都是上一层已经计算过的一个子串的排名

具体得看代码实现，复杂度为 \(O(n\log n)\)

// 这里是定义：
// c 表示桶，每一个对应着这一个桶所对应的数的个数，前缀和即是排名
// s 是要计算 SA 的字符串

inline void get_SA() {
    rep(i, 1, n) c[x[i] = s[i]]++;
    rep(i, 2, m) c[i] += c[i - 1];
    rep(i, n, 1) sa[c[x[i]]--] = i; // 编号为 i 的物品在当前长度下排名为 c[x[i]]
    // 然后由于当前排名的物品使用了一个，所以排名上移一位（一开始的排名是最下面的排名）
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        rep(i, n - k + 1, n) y[++num] = i; // 这一部分没有“第二个字符”，所以在最前面
        rep(i, 1, n) if (sa[i] > k) y[++num] = sa[i] - k; // 如果一个串的结束位置在 k 之后，那么这个串一定可以作为另一个串的后一半
        rep(i, 1, m) c[i] = 0;
        rep(i, 1, n) c[x[i]]++;
        rep(i, 2, m) c[i] += c[i - 1];
        rrep(i, n, 1) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1;
        rep(i, 1, n)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if (num == n) break;
        m = num;
    }
}

后缀数组学习笔记

原文：https://www.cnblogs.com/wawawa8/p/10344418.html