后缀数组学习笔记

后缀数组学习笔记

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

赶快学习一发

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

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

大概实现就是首先按照第二维排序，最小的肯定是没有第二维的那些，然后按照上一次排序的结果一个个扫过去，如果这个子串可以作为某一个当前正在处理的子串的后一半（sa[i]>k）那么就塞进桶里。

然后按照第一维排序，

具体得看代码实现，复杂度为 (O(nlog 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; // 按照 y 的倒序将 x 插入至 sa 中，保证有序
       	swap(x, y); // x[i] 表示以 i 开头的子串的排名，y[i] 表示上一轮以 i 开始的子串的排名
        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;
    }
}

这样我们就求出了数组 ( ext{SA})

还剩下一个数组 ( ext{height})，表示 ( ext{suffix[i-1]}) 与 ( ext{suffix[i]}) 之间的 ( ext{lcp}) 长度，不难 ( ext{yy}) 出来，如果我们将后缀排序之后，两个串的 ( ext{lcp})，事实上也是排完序后这两个串之间所有串的共同前缀，所以现在如果要求 ( ext{suffix[i]}) 和 ( ext{suffix[j]}) 的 ( ext{lcp})，事实上长度就是 $$min_{k=i}^jleft { height[k] ight }$$

发现一个性质，(height[rank[i+1]] geq height[rank[i]]-1)

证明：

设 (suffix[k]) 是排在 (suffix[i]) 前一名的后缀

那么他们的最长公共前缀的长度就是 (height[rank[i]])，不妨设这个长度 (gt 1)

那么(suffix[k+1]) 将排在 (suffix[i +1]) 前面（但是不一定是前一个），并且这两个串的 ( ext{lcp}) 是 (height[rank[i]]-1)，而又有这两个串的 ( ext{lcp}) 长度等于 (min_{x=rank[k+2]}^{rank[i+1]}left { height[x] ight })，其中包含了 (height[rank[i+1]]) 这一项，由此证明了 (height[rank[i+1]]geq height[rank[i]]-1)

由此性质得证

这意味着什么呢？我们直接按照 (rank) 的顺序求 (height) 数组，即可以做到线性

rep(i, 1, n) rank[sa[i]] = i;
int j = 0;
rep(i, 1, n) {
    if (j) j--;
    while (a[i + j] == a[sa[rank[i] - 1] + j]) j++; // 暴力枚举 height，由于之前的性质复杂度是对的
    height[rank[i]] = j;
}