企业官网建设流程全解析

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

在高级字符串算法、生物信息学 DNA 碱基序列比对、海量代码重复子串挖掘以及搜索引擎后缀检索中，“后缀数组（Suffix Array，简称 SA）”是在空间和常数效率上全面超越后缀树（Suffix Tree）的顶级数据结构。

经典高级算法题型包括：

• LeetCode 1044：最长重复子串（Longest Duplicate Substring）；
• LeetCode 1062：最长重复子串 II；
• LeetCode 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_{i+1} \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^{k+1}$

如果直接对 $N$ 个后缀进行快速排序，单次比对需要 $O(N)$，总时间复杂度为 $O(N^2 \log N)$。
倍增算法采用**“双关键字排序”**思想，将时间复杂度压缩至$\mathcal{O}(N \log N)$！

graph TD Round0[阶段 0: 按单字符 2^0=1 排序, 得到第一轮排名 rk] --> Round1[阶段 1: 比较长度 2^1=2 的子串] Round1 --> Step1[第一关键字: 前半段长度 2^0 的排名 rk[i]] Round1 --> Step2[第二关键字: 后半段长度 2^0 的排名 rk[i + 2^0] (越界设为 0)] Step1 & Step2 --> RadixSort[基数排序 / 快速排序合并为新的 2 长度排名] Round1 --> Round2[阶段 2: 递推比较长度 2^2=4 的子串 (第一关键字长2, 第二关键字长2)] Round2 --> RoundK[递归进行 log N 轮, 完成全后缀精确排序!]

三、Height 数组与 Kasai 算法：$\mathcal{O}(N)$ 线性构造引理

Height 数组记录了字典序相邻的两个后缀的最长公共前缀长度（LCP，Longest 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[i+len] 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); } }

经典应用场景速查

实习生的算法总结

后缀数组是字符串处理领域中“将离散子串全景排序”的集大成者。
通过倍增算法将单字符扩张为整体拓扑，再通过 Kasai 引理将前缀重叠计算线性化。
掌握了后缀数组与 Height 数组的联合运用，任何关于多串公共子串、重复模式挖掘与最长前缀的问题，都将迎刃而解。