引言
后缀树（Suffix Tree）是处理字符串问题的强大数据结构，它将一个字符串的所有后缀组织成一棵压缩的字典树。对于一个长度为n的字符串，其后缀树包含n个叶节点（对应n个后缀），且可以在O(n)时间和空间内构造。
后缀树支持多种经典字符串操作：子串存在性查询、最长重复子串、最长公共子串、最长回文子串等，均可在O(n)预处理后以O(m)或更优的时间回答（m为查询模式长度）。
Ukkonen算法是后缀树的经典在线构造算法，它从左到右逐个字符构建后缀树，整个构造过程的时间复杂度为O(n)。本文将用Java完整实现Ukkonen算法，并展示最长公共子串等核心应用。
核心原理
后缀树定义
字符串S的后缀树是一棵满足以下条件的压缩字典树：
1. 每条边标记为S的一个非空子串
2. 从根到叶的路径对应S的一个后缀
3. 每个内部节点至少有两个子节点
Ukkonen算法三要素
-
活动点（Active Point）：当前处理阶段中，代表所有需要扩展后缀的共同前缀的位置，由三元组(active_node, active_edge, active_length)表示。
-
剩余后缀数（Remainder）：当前阶段还需要插入的新后缀数量。
-
后缀链接（Suffix Link）：内部节点间的指针，加速遍历。若节点v代表子串xα，则其后缀链接指向代表α的节点。
在线构造思想
算法逐个处理字符S[i]。对于每个字符，需要将所有尚未结束的后缀（数量为remainder）进行扩展。通过活动点机制，大部分扩展可在O(1)时间内完成。
Java实现
import java.util.*;
/**
* 后缀树节点
*/
class SuffixTreeNode {
// 边标签对应的字符串区间 [start, end)
// end使用特殊值END（如Integer.MAX_VALUE）表示叶子节点的开放边
int start;
int end;
SuffixTreeNode parent;
Map<Character, SuffixTreeNode> children;
SuffixTreeNode suffixLink; // 后缀链接
int suffixIndex; // 叶节点对应的后缀起始位置，-1表示非叶节点
public SuffixTreeNode(int start, int end, SuffixTreeNode parent) {
this.start = start;
this.end = end;
this.parent = parent;
this.children = new HashMap<>();
this.suffixLink = null;
this.suffixIndex = -1;
}
/**
* 获取边长度
*/
public int edgeLength() {
return end - start;
}
/**
* 获取边的字符串表示（用于调试）
*/
public String getEdgeString(String text) {
return text.substring(start, Math.min(end, text.length()));
}
}
/**
* Ukkonen后缀树构造器
*/
class SuffixTree {
private final String text;
private final SuffixTreeNode root;
private SuffixTreeNode activeNode;
private char activeEdge;
private int activeLength;
private int remainder;
private int leafEnd; // 全局叶子结束位置，所有叶节点共享
public SuffixTree(String text) {
this.text = text + "$"; // 添加唯一结束符
this.root = new SuffixTreeNode(-1, -1, null);
this.activeNode = root;
this.activeEdge = '\0';
this.activeLength = 0;
this.remainder = 0;
this.leafEnd = -1;
build();
}
/**
* 获取活动边指向的子节点
*/
private SuffixTreeNode getActiveEdgeNode() {
if (activeEdge == '\0') return null;
return activeNode.children.get(activeEdge);
}
/**
* 从活动点沿边向下走，必要时分割边
*/
private boolean walkDown(SuffixTreeNode node) {
if (activeLength >= node.edgeLength()) {
activeEdge = text.charAt(node.start + activeLength);
activeLength -= node.edgeLength();
activeNode = node;
return true;
}
return false;
}
/**
* 构建后缀树（Ukkonen算法）
*/
private void build() {
for (int i = 0; i < text.length(); i++) {
extend(i);
}
// 设置后缀索引
setSuffixIndex(root, 0);
}
/**
* 执行第i阶段的扩展
*/
private void extend(int i) {
char currentChar = text.charAt(i);
leafEnd = i + 1;
remainder++;
SuffixTreeNode lastNewNode = null;
while (remainder > 0) {
if (activeLength == 0) {
activeEdge = currentChar;
}
SuffixTreeNode next = getActiveEdgeNode();
if (next == null) {
// 规则1：创建新的叶节点
activeNode.children.put(activeEdge,
new SuffixTreeNode(i, Integer.MAX_VALUE, activeNode));
if (lastNewNode != null) {
lastNewNode.suffixLink = activeNode;
lastNewNode = null;
}
} else {
if (walkDown(next)) {
continue; // 从新的活动点重新开始
}
// 检查当前字符是否已在边上
char edgeChar = text.charAt(next.start + activeLength);
if (edgeChar == currentChar) {
// 规则3：当前后缀已存在，停止本阶段
if (lastNewNode != null && activeNode != root) {
lastNewNode.suffixLink = activeNode;
lastNewNode = null;
}
activeLength++;
break;
}
// 规则2：分裂边
int splitPos = next.start + activeLength;
SuffixTreeNode split = new SuffixTreeNode(next.start, splitPos, next.parent);
activeNode.children.put(activeEdge, split);
// 新的叶节点
split.children.put(currentChar,
new SuffixTreeNode(i, Integer.MAX_VALUE, split));
// 原边成为split的子节点
next.start = splitPos;
next.parent = split;
split.children.put(text.charAt(next.start), next);
if (lastNewNode != null) {
lastNewNode.suffixLink = split;
}
lastNewNode = split;
}
remainder--;
if (activeNode == root && activeLength > 0) {
activeLength--;
activeEdge = text.charAt(i - remainder + 1);
} else if (activeNode != root) {
activeNode = activeNode.suffixLink != null ? activeNode.suffixLink : root;
}
}
}
/**
* 递归设置叶节点的后缀索引
*/
private int setSuffixIndex(SuffixTreeNode node, int labelHeight) {
if (node == null) return 0;
boolean isLeaf = true;
for (SuffixTreeNode child : node.children.values()) {
isLeaf = false;
setSuffixIndex(child, labelHeight + child.edgeLength());
}
if (isLeaf) {
// 叶节点对应后缀 text[start - labelHeight + edgeLength :]
// 由于叶节点边开放到无穷，edgeLength = leafEnd - start
// 但leafEnd在构造完成后等于text.length()
// 所以 suffixIndex = leafEnd - labelHeight
node.suffixIndex = text.length() - labelHeight;
// 去掉结束符$的影响
if (node.suffixIndex == text.length() - 1) {
node.suffixIndex = -1; // 仅包含$的后缀，忽略
}
}
return 0;
}
/**
* 搜索模式是否存在
*/
public boolean contains(String pattern) {
SuffixTreeNode current = root;
int i = 0;
while (i < pattern.length()) {
SuffixTreeNode child = current.children.get(pattern.charAt(i));
if (child == null) return false;
String edgeStr = text.substring(child.start,
Math.min(child.end, text.length()));
String remainingPattern = pattern.substring(i);
if (remainingPattern.startsWith(edgeStr)) {
i += edgeStr.length();
current = child;
} else if (edgeStr.startsWith(remainingPattern)) {
return true;
} else {
return false;
}
}
return true;
}
/**
* 查找最长重复子串
*/
public String longestRepeatedSubstring() {
Result result = new Result();
findLRS(root, 0, result);
return result.bestString;
}
private void findLRS(SuffixTreeNode node, int depth, Result result) {
if (node == null) return;
// 叶节点
if (node.children.isEmpty()) return;
// 检查该节点下是否有至少两个不同的后缀
int leafCount = countLeaves(node);
if (leafCount >= 2 && depth > result.bestLength) {
result.bestLength = depth;
result.bestString = getPathString(node, depth);
}
for (SuffixTreeNode child : node.children.values()) {
findLRS(child, depth + child.edgeLength(), result);
}
}
private int countLeaves(SuffixTreeNode node) {
if (node.children.isEmpty()) return 1;
int count = 0;
for (SuffixTreeNode child : node.children.values()) {
count += countLeaves(child);
}
return count;
}
private String getPathString(SuffixTreeNode node, int depth) {
// 从根到node的路径对应的字符串
StringBuilder sb = new StringBuilder();
SuffixTreeNode curr = node;
List<SuffixTreeNode> path = new ArrayList<>();
while (curr != root && curr != null) {
path.add(curr);
curr = curr.parent;
}
Collections.reverse(path);
for (SuffixTreeNode n : path) {
sb.append(text, n.start, Math.min(n.end, text.length()));
}
return sb.toString();
}
static class Result {
int bestLength = 0;
String bestString = "";
}
/**
* 查找两个字符串的最长公共子串
*/
public static String longestCommonSubstring(String s1, String s2) {
String combined = s1 + "#" + s2 + "$";
SuffixTree tree = new SuffixTree(combined);
return tree.findLCS(s1.length(), s1.length() + 1 + s2.length());
}
private String findLCS(int s1Len, int totalLen) {
Result result = new Result();
findLCSHelper(root, 0, s1Len, result);
return result.bestString;
}
private boolean[] findLCSHelper(SuffixTreeNode node, int depth, int s1Len, Result result) {
if (node == null) return new boolean[]{false, false};
if (node.children.isEmpty()) {
boolean inS1 = node.suffixIndex >= 0 && node.suffixIndex < s1Len;
boolean inS2 = node.suffixIndex > s1Len;
return new boolean[]{inS1, inS2};
}
boolean hasS1 = false, hasS2 = false;
for (SuffixTreeNode child : node.children.values()) {
boolean[] childRes = findLCSHelper(child, depth + child.edgeLength(), s1Len, result);
hasS1 |= childRes[0];
hasS2 |= childRes[1];
}
if (hasS1 && hasS2 && depth > result.bestLength) {
result.bestLength = depth;
result.bestString = getPathString(node, depth);
}
return new boolean[]{hasS1, hasS2};
}
public SuffixTreeNode getRoot() { return root; }
public String getText() { return text; }
}
/**
* 后缀树应用演示
*/
public class SuffixTreeDemo {
public static void main(String[] args) {
// 基础构造测试
String text = "banana";
System.out.println("=== 后缀树构造 ===");
System.out.println("原始字符串: " + text);
SuffixTree tree = new SuffixTree(text);
System.out.println("后缀树构造完成");
// 子串查询
System.out.println("\n=== 子串查询 ===");
String[] queries = {"ana", "na", "baa", "a", "ban"};
for (String q : queries) {
System.out.println("包含 '" + q + "': " + tree.contains(q));
}
// 最长重复子串
System.out.println("\n=== 最长重复子串 ===");
String lrs = tree.longestRepeatedSubstring();
System.out.println("最长重复子串: '" + lrs + "'");
// 另一个例子
String text2 = "abacabadabacabae";
System.out.println("\n字符串: " + text2);
SuffixTree tree2 = new SuffixTree(text2);
System.out.println("最长重复子串: '" + tree2.longestRepeatedSubstring() + "'");
// 最长公共子串
System.out.println("\n=== 最长公共子串 ===");
String s1 = "ABABC";
String s2 = "BABCA";
String lcs = SuffixTree.longestCommonSubstring(s1, s2);
System.out.println("s1: " + s1);
System.out.println("s2: " + s2);
System.out.println("最长公共子串: '" + lcs + "'");
String s3 = "GeeksforGeeks";
String s4 = "GeeksQuiz";
System.out.println("\ns3: " + s3);
System.out.println("s4: " + s4);
System.out.println("最长公共子串: '" + SuffixTree.longestCommonSubstring(s3, s4) + "'");
// 性能测试
System.out.println("\n=== 性能测试 ===");
int[] sizes = {1000, 5000, 10000, 50000};
Random rand = new Random(42);
for (int n : sizes) {
StringBuilder sb = new StringBuilder(n);
for (int i = 0; i < n; i++) {
sb.append((char) ('a' + rand.nextInt(4)));
}
String testStr = sb.toString();
long start = System.nanoTime();
SuffixTree st = new SuffixTree(testStr);
long time = System.nanoTime() - start;
System.out.printf("n=%d: 构造时间=%.2fms%n", n, time / 1e6);
}
}
}
算法分析
时间复杂度
Ukkonen算法的每个阶段（处理一个字符）中，规则3（停止扩展）最多执行一次，其余扩展均通过规则1或规则2完成。关键观察：
- 活动点深度（从根到活动点的路径长度）总增量为O(n)
- 后缀链接跳转使活动点深度不会无限增加
- 每阶段均摊扩展次数为O(1)
因此总时间复杂度为 O(n)，其中n为字符串长度。
空间复杂度
后缀树最多有2n-1个节点（n个叶节点和最多n-1个内部节点），每个节点存储常数个指针/整数。总空间复杂度为 O(n)。
应用场景对比
| 问题 | 使用后缀树 | 替代方案 |
|---|---|---|
| 子串存在性查询 | O(m) | KMP: O(n + m) |
| 最长重复子串 | O(n) | 后缀数组 + LCP: O(n log n) |
| 最长公共子串（两串） | O(n + m) | 动态规划: O(nm) |
| 不同子串计数 | O(n) | 后缀自动机: O(n) |
扩展思考
- 后缀自动机：与后缀树等价但空间更紧凑的数据结构，特别适合处理大量子串计数问题。
- 广义后缀树：为多个字符串构建公共后缀树，支持多串最长公共子串等高级查询。
- 在线查询：结合LCA（最低公共祖先）和RMQ（区间最值查询），可在O(1)时间内回答最长公共前缀查询。
总结
后缀树是字符串算法领域的核心数据结构，Ukkonen算法以优雅的在线构造策略实现了线性时间复杂度。通过后缀树，大量看似复杂的字符串问题（最长重复子串、最长公共子串等）都能被高效解决。理解后缀树的构造和应用，是掌握高级字符串处理技术的重要基石。
