第41章后缀数组与后缀树

课程目录第41章后缀数组与后缀树

第41章后缀数组与后缀树：从字符串匹配到基因序列分析

说实话，字符串处理这块，很多初学者觉得不就是找找子串、比对比对嘛。但当你真正面对一个几百万字符的文本，或者要处理DNA序列这种超长字符串时，传统方法就彻底歇菜了。这时候，后缀数组和后缀树就是你的救命稻草。

我个人最早接触后缀数组是在做基因序列比对的项目里。当时要在一段长达千万级的基因组中快速查找某个模式串，暴力匹配跑了一整天都没出结果。后来换了后缀数组，配合LCP，几分钟就搞定了。嗯，从那以后我就再也没小看过这个数据结构。

后缀数组的定义

先说说什么是后缀数组。说白了，就是把一个字符串的所有后缀按字典序排个序，然后记录下每个后缀在原串中的起始位置。

举个例子，字符串 "banana" 的后缀有：

banana
anana
nana
ana
na
a

按字典序排序后变成：

a        → 起始位置 5
ana      → 起始位置 3
anana    → 起始位置 1
banana   → 起始位置 0
na       → 起始位置 4
nana     → 起始位置 2

所以后缀数组就是 [5, 3, 1, 0, 4, 2]。

核心思想：后缀数组本身不存字符串，只存索引。通过索引可以快速定位到任意后缀，配合二分查找就能高效完成模式匹配。

倍增法构造后缀数组

构造后缀数组最经典的方法就是倍增法。为什么叫倍增？因为它每次利用已经排好的长度为 k 的排名，去推长度为 2k 的排名。你想想看，这就像滚雪球一样，越滚越大。

我当年第一次看倍增法代码时，觉得这玩意儿太绕了。后来自己手写了一遍才明白，其实就是个基数排序的变种。

// 倍增法构造后缀数组
void build_sa(int *s, int *sa, int n, int m) {
    int *rk = new int[n], *tmp = new int[n];
    int *cnt = new int[m + 1];
    
    // 第一轮：按单个字符排序
    for (int i = 0; i < m; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[s[i]]] = i;
    
    // 倍增过程
    for (int k = 1; k < n; k *= 2) {
        // 按第二关键字排序
        int p = 0;
        for (int i = n - k; i < n; i++) tmp[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) tmp[p++] = sa[i] - k;
        
        // 按第一关键字排序
        for (int i = 0; i < m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) 
            sa[--cnt[rk[tmp[i]]]] = tmp[i];
        
        // 更新排名
        swap(rk, tmp);
        rk[sa[0]] = 0;
        p = 1;
        for (int i = 1; i < n; i++)
            rk[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] &&
                        tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? p - 1 : p++;
        if (p >= n) break;
        m = p;
    }
    
    delete[] rk; delete[] tmp; delete[] cnt;
}

我的经验：倍增法的时间复杂度是 O(n log n)，空间复杂度 O(n)。对于大多数场景已经够用了。但如果你要处理上亿级别的数据，可以考虑 DC3 算法，它是 O(n) 的，不过常数比较大。

DC3算法：线性时间的构造

DC3（Difference Cover Mod 3）算法，也叫 skew 算法。它把后缀分成三组，递归处理，最后合并。说实话，这个算法我很少在实际项目中手写，因为实现起来太复杂了。但理解它的思想很重要——分治策略在字符串处理中的妙用。

DC3的核心步骤：

将后缀按起始位置 mod 3 分成三组：S0、S1、S2
递归构造 S1∪S2 的后缀数组
利用 S1∪S2 的结果构造 S0 的后缀数组
合并三个数组

避坑指南：我曾经在实现 DC3 时踩过一个坑——递归调用时字符集大小没处理好，导致排序结果全乱了。记住，递归时要把三元组映射成新的字符，字符集大小要重新计算。

LCP与RMQ：后缀数组的灵魂搭档

光有后缀数组还不够，很多时候我们需要知道两个后缀的最长公共前缀（LCP）。比如你要找两个字符串的最长公共子串，或者做模式匹配时的加速，都离不开 LCP。

LCP 数组的定义很简单：lcp[i] 表示排名第 i 的后缀和排名第 i-1 的后缀的最长公共前缀长度。

计算 LCP 有个经典算法——Kasai 算法，O(n) 搞定：

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

有了 LCP 数组，再配合 RMQ（区间最小值查询），就能在 O(1) 时间内回答任意两个后缀的 LCP。你想想看，这意味着什么？意味着你可以快速比较任意两个子串的大小关系。

实用技巧：我一般用稀疏表（Sparse Table）来实现 RMQ，预处理 O(n log n)，查询 O(1)。对于静态的 LCP 数组，这是最优选择。

后缀树：从数组到树形结构

后缀树是后缀数组的"升级版"。它把字符串的所有后缀压缩成一棵树，每个叶子节点对应一个后缀，每条边对应一段子串。

为什么需要后缀树？因为有些操作在后缀数组上做比较麻烦，比如查找一个模式串的所有出现位置。在后缀树上，你只需要沿着树边走，找到对应节点，然后遍历它的子树就能得到所有匹配位置。

我画了一张图，帮你理解后缀数组和后缀树的关系：

后缀树的实际应用

后缀树的应用场景非常广泛，我挑几个常见的说说：

模式匹配：在 O(m) 时间内查找模式串，其中 m 是模式串长度。比 KMP 还快，而且支持同时查找多个模式串。
最长重复子串：在后缀树上找最深的内节点，对应的路径就是最长重复子串。我在做日志分析时用过这个功能，快速定位重复出现的错误信息。
最长公共子串：把两个字符串拼起来，中间加个特殊字符，建后缀树。然后找同时属于两个字符串的最深节点。
DNA序列比对：这是后缀树的大杀器。基因序列动辄上亿字符，后缀树能高效完成序列比对、变异检测等任务。

我的建议：如果你只是做算法题或者中小规模的数据处理，后缀数组完全够用。但如果你要处理超大规模文本，或者需要频繁进行模式匹配，后缀树更合适。不过后缀树的内存开销比较大，每个节点要存 26 个（或更多）子节点指针，实际使用时要注意优化。

总结一下

后缀数组和后缀树是字符串处理领域的两大神器。后缀数组简洁高效，配合 LCP 和 RMQ 能解决大部分问题。后缀树功能更强大，但实现复杂、内存开销大。我个人建议：先从后缀数组入手，把倍增法和 Kasai 算法写熟练了，再考虑后缀树。

记住一句话：没有银弹。选哪个取决于你的具体场景。数据量小用暴力也不怕，数据量大就得靠这些高级数据结构了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录