后缀数组（Suffix Array）与倍增算法（Doubling Algorithm）：后缀排序、Height 数组与最长公共前缀（LCP）实战

后缀数组Suffix Array与倍增算法Doubling Algorithm后缀排序、Height 数组与最长公共前缀LCP实战在高级字符串算法、生物信息学 DNA 碱基序列比对、海量代码重复子串挖掘以及搜索引擎后缀检索中“后缀数组Suffix Array简称 SA”是在空间和常数效率上全面超越后缀树Suffix Tree的顶级数据结构。经典高级算法题型包括LeetCode 1044最长重复子串Longest Duplicate SubstringLeetCode 1062最长重复子串 IILeetCode 1163按字典序排在最后的子串多模式串最长公共子串LCS与本质不同子串个数统计。很多同学知道后缀数组强大但在面对倍增算法Doubling Algorithm与Height 数组的最长公共前缀LCP时往往被繁琐的双关键字基数排序与递推引理绕晕。今天我们用极其清晰的几何图解把倍增算法推导、Height 数组的 $O(N)$ 线性构造引理Kasai 算法以及工业级模板彻底讲透。一、后缀数组核心三大数组定义对于长度为 $N$ 的字符串 $S s_0 s_1 \dots s_{n-1}$其后缀 $\text{Suffix}(i)$ 表示从索引 $i$ 开始到末尾的子串 $s_i s_{i1} \dots s_{n-1}$。将所有 $N$ 个后缀按字典序从小到大排序后graph LR subgraph 三大核心映射数组 SA[1. sa[i]: 排名为 i 的后缀在原字符串中的起始索引 (从名次查位置)] Rank[2. rk[i]: 起始索引为 i 的后缀在所有后缀中的名次 (从位置查名次, sa 与 rk 互为反函数!)] Height[3. height[i]: 排名第 i 的后缀与排名第 i-1 的后缀的最长公共前缀长度 (LCP(sa[i], sa[i-1]))] end二、倍增算法Doubling Algorithm从长度 $2^k$ 递推到 $2^{k1}$如果直接对 $N$ 个后缀进行快速排序单次比对需要 $O(N)$总时间复杂度为 $O(N^2 \log N)$。倍增算法采用**“双关键字排序”**思想将时间复杂度压缩至$\mathcal{O}(N \log N)$graph TD Round0[阶段 0: 按单字符 2^01 排序, 得到第一轮排名 rk] -- Round1[阶段 1: 比较长度 2^12 的子串] Round1 -- Step1[第一关键字: 前半段长度 2^0 的排名 rk[i]] Round1 -- Step2[第二关键字: 后半段长度 2^0 的排名 rk[i 2^0] (越界设为 0)] Step1 Step2 -- RadixSort[基数排序 / 快速排序合并为新的 2 长度排名] Round1 -- Round2[阶段 2: 递推比较长度 2^24 的子串 (第一关键字长2, 第二关键字长2)] Round2 -- RoundK[递归进行 log N 轮, 完成全后缀精确排序!]三、Height 数组与 Kasai 算法$\mathcal{O}(N)$ 线性构造引理Height 数组记录了字典序相邻的两个后缀的最长公共前缀长度LCPLongest Common Prefix$$\mathbf{\text{height}[i] \text{LCP}(\text{Suffix}(sa[i]), \ \text{Suffix}(sa[i-1]))}$$核心性质任意两个后缀的最长公共前缀等于区间 Height 的最小值$$\mathbf{\text{LCP}(\text{Suffix}(sa[i]), \ \text{Suffix}(sa[j])) \min_{i k \le j} \text{height}[k]}$$Kasai 关键引理保证线性推导设 $h[i] \text{height}[rk[i]]$即原串中位置 $i$ 开始的后缀的 Height 值则必然满足$$\mathbf{h[i] \ge h[i-1] - 1}$$物理含义当原串索引从 $i-1$ 移动到 $i$ 时新的最长公共前缀长度最多减少 1利用这个单调性我们在匹配时不需要从 0 开始重新比对直接从 $h[i-1]-1$ 开始继续向后比对指针最多回退 $N$ 步计算整个 Height 数组的时间复杂度收敛为严格的$\mathcal{O}(N)$工业级后缀数组 Java 完整实现模板LeetCode 1044 最长重复子串import java.util.Arrays; public class SuffixArray { private final String s; private final int n; public int[] sa; // 排名为 i 的后缀起始索引 public int[] rk; // 起始索引为 i 的后缀排名 public int[] height; // 字典序相邻后缀的最长公共前缀 public SuffixArray(String s) { this.s s; this.n s.length(); this.sa new int[n]; this.rk new int[n]; this.height new int[n]; buildSA(); buildHeight(); } private void buildSA() { Integer[] saObj new Integer[n]; for (int i 0; i n; i) { saObj[i] i; rk[i] (int) s.charAt(i); // 第一轮按 ASCII 码初始化排名 } // 倍增排序 for (int k 1; k n; k * 2) { final int len k; final int[] currentRk rk.clone(); // 双关键字排序第一关键字 currentRk[i], 第二关键字 currentRk[ilen] Arrays.sort(saObj, (a, b) - { if (currentRk[a] ! currentRk[b]) { return Integer.compare(currentRk[a], currentRk[b]); } int rka (a len n) ? currentRk[a len] : -1; int rkb (b len n) ? currentRk[b len] : -1; return Integer.compare(rka, rkb); }); // 重新计算离散化排名 rk[saObj[0]] 0; for (int i 1; i n; i) { int prev saObj[i - 1]; int curr saObj[i]; boolean isSame (currentRk[prev] currentRk[curr]) ((prev len n ? currentRk[prev len] : -1) (curr len n ? currentRk[curr len] : -1)); rk[curr] rk[prev] (isSame ? 0 : 1); } if (rk[saObj[n - 1]] n - 1) { break; // 排名全部唯一提前收敛退出 } } for (int i 0; i n; i) { sa[i] saObj[i]; } } private void buildHeight() { int k 0; for (int i 0; i n; i) { if (rk[i] 0) { height[0] 0; continue; } int j sa[rk[i] - 1]; // 字典序排在 i 前一名的后缀起始位置 if (k 0) k--; // Kasai 引理k 最多减少 1 while (i k n j k n s.charAt(i k) s.charAt(j k)) { k; // 线性向后匹配 } height[rk[i]] k; } } // 求解最长重复子串 public String getLongestDuplicateSubstring() { int maxLen 0; int startIdx 0; for (int i 1; i n; i) { if (height[i] maxLen) { maxLen height[i]; startIdx sa[i]; } } return maxLen 0 ? : s.substring(startIdx, startIdx maxLen); } }经典应用场景速查经典字符串问题基于后缀数组的最优解法复杂度最长重复子串求height数组中的最大值及其对应的sa[i]$\mathcal{O}(N \log N)$最长公共子串LCS将两串用特殊字符#拼接求相邻且属于不同原串的height最大值$\mathcal{O}(N \log N)$本质不同子串总个数全串子串总数 $\frac{N(N1)}{2} - \sum \text{height}[i]$$\mathcal{O}(N \log N)$实习生的算法总结后缀数组是字符串处理领域中“将离散子串全景排序”的集大成者。通过倍增算法将单字符扩张为整体拓扑再通过 Kasai 引理将前缀重叠计算线性化。掌握了后缀数组与 Height 数组的联合运用任何关于多串公共子串、重复模式挖掘与最长前缀的问题都将迎刃而解。