深入理解Java后缀树（从零开始构建高效字符串匹配结构）

为什么学习后缀树？

掌握后缀树实现有助于你深入理解高级字符串算法。虽然实际项目中可能直接使用现成库，但亲手实现能极大提升你的算法思维和编码能力。

用Java构建简易后缀树

我们将采用最直观的方式——为每个后缀插入到 Trie 中，再进行压缩（简化）。虽然这不是最优的 Ukkonen 算法（O(n) 时间复杂度），但对于学习目的足够清晰。

步骤 1：定义树节点

class SuffixTreeNode {    char character;    Map children = new HashMap<>();    boolean isEndOfWord = false;    public SuffixTreeNode(char c) {        this.character = c;    }}

步骤 2：构建后缀树类

public class SuffixTree {    private SuffixTreeNode root;    public SuffixTree(String text) {        // 添加唯一终止符以确保所有后缀唯一        text += "$";        root = new SuffixTreeNode('\0'); // 根节点无字符        // 为每个后缀插入到树中        for (int i = 0; i < text.length(); i++) {            insertSuffix(text.substring(i));        }    }    private void insertSuffix(String suffix) {        SuffixTreeNode current = root;        for (char c : suffix.toCharArray()) {            current.children.putIfAbsent(c, new SuffixTreeNode(c));            current = current.children.get(c);        }        current.isEndOfWord = true;    }    // 检查子串是否存在    public boolean contains(String substring) {        SuffixTreeNode current = root;        for (char c : substring.toCharArray()) {            if (!current.children.containsKey(c)) {                return false;            }            current = current.children.get(c);        }        return true;    }}

步骤 3：测试代码

public class Main {    public static void main(String[] args) {        SuffixTree tree = new SuffixTree("banana");        System.out.println(tree.contains("ana"));  // true        System.out.println(tree.contains("nan"));  // true        System.out.println(tree.contains("xyz"));  // false    }}

进阶提示

上述实现时间复杂度为 O(n²)，适用于教学。若需工业级性能，请研究 Ukkonen 算法，它能在 O(n) 时间内构建后缀树。这也是许多字符串算法竞赛题的核心技巧。

总结

通过本篇后缀树教程，你已掌握了后缀树的基本原理与 Java 实现方法。虽为简化版，但足以应对多数学习场景。建议你动手修改代码，尝试添加“查找最长重复子串”等功能，进一步巩固理解。

关键词回顾：Java后缀树、后缀树实现、字符串算法、后缀树教程。