引言
回文子串的统计和处理是字符串算法中的经典问题。传统的暴力方法时间复杂度为 O(n²) 或更高，难以应对大规模数据。回文自动机（Palindromic Tree），又称 Eertree，是 2014 年提出的一种专门处理回文子串的数据结构。它能在 O(n) 时间内统计一个字符串中所有不同的回文子串，并支持快速查询。本文将用 Java 完整实现回文自动机，并展示其在回文子串计数、最长回文后缀等场景中的应用。
回文自动机的结构
回文自动机由两种根节点和若干状态组成：
双根设计
- 偶根（Even Root）：表示长度为 0 的空回文串，编号通常为 0
- 奇根（Odd Root）：表示长度为 -1 的虚拟节点，编号通常为 1
这种看似奇怪的设计有着精妙的用意：奇根的长度为 -1，使得任何字符都可以作为长度为 1 的回文串的”中心”扩展出来。
状态表示
每个状态（节点）代表一个不同的回文子串，包含以下信息：
– length：该回文串的长度
– suffixLink：指向该回文串的最长真回文后缀对应的状态
– next：转移数组/映射，表示在当前回文串两侧添加某个字符后形成的新回文串
– occurrences：该回文串在字符串中出现的次数
核心算法思想
回文自动机的构建是增量式的：从左到右扫描字符串，每次添加一个字符，利用已有的回文信息快速定位新回文串。
增量构建过程
对于每个位置 i 的字符 c：
- 定位插入点：从上一个插入的状态出发，沿着 suffixLink 跳转，直到找到一个状态，使得其对应回文串的前一个字符等于 c
- 检查回文串是否已存在：若该状态的 next 中已有字符 c 的转移，则直接返回该状态
- 创建新状态：否则创建一个新状态，表示在当前回文串两侧添加 c 后形成的新回文串
- 计算新状态的 suffixLink：若新状态长度为 1，则 suffixLink 指向奇根；否则继续沿着 suffixLink 跳转，找到新状态的最长真回文后缀
Java 完整实现
import java.util.*;
/**
* 回文自动机（Palindromic Tree / Eertree）
* 用于高效统计字符串中所有不同的回文子串
*/
public class PalindromicTree {
/**
* 回文自动机节点
*/
static class Node {
int length; // 回文串长度
int suffixLink; // 后缀链接（最长真回文后缀）
Map<Character, Integer> next; // 转移：字符 -> 状态编号
long occurrences; // 出现次数（需后续传播）
public Node(int length) {
this.length = length;
this.suffixLink = 0;
this.next = new HashMap<>();
this.occurrences = 0;
}
}
private List<Node> tree; // 自动机状态列表
private String s; // 当前处理的字符串
private int last; // 上一个插入的状态编号
private int size; // 当前字符串长度
// 根节点常量
private static final int EVEN_ROOT = 0; // 偶根，长度0
private static final int ODD_ROOT = 1; // 奇根，长度-1
public PalindromicTree() {
this.tree = new ArrayList<>();
this.s = "";
this.last = 0;
this.size = 0;
// 初始化偶根（长度0）
tree.add(new Node(0));
tree.get(EVEN_ROOT).suffixLink = EVEN_ROOT;
// 初始化奇根（长度-1）
tree.add(new Node(-1));
tree.get(ODD_ROOT).suffixLink = ODD_ROOT;
}
/**
* 获取回文自动机的状态数量（即不同回文子串的数量 + 2个根）
*/
public int getNodeCount() {
return tree.size();
}
/**
* 获取不同回文子串的数量
*/
public int distinctPalindromeCount() {
return tree.size() - 2; // 减去两个根节点
}
/**
* 获取最长回文后缀对应的状态编号
*/
public int getLast() {
return last;
}
/**
* 获取特定状态对应的回文串长度
*/
public int getLength(int state) {
return tree.get(state).length;
}
/**
* 核心：添加一个字符并更新回文自动机
* @param c 要添加的字符
* @return 新创建或复用的状态编号
*/
public int addChar(char c) {
s += c;
size++;
// 步骤1：找到插入点
int cur = last;
int curLen;
while (true) {
curLen = tree.get(cur).length;
// 检查位置 size - 1 - curLen - 1 是否合法且字符匹配
if (size - 1 - curLen - 1 >= 0 && s.charAt(size - 1 - curLen - 1) == c) {
break;
}
cur = tree.get(cur).suffixLink;
}
// 步骤2：检查该回文串是否已存在
if (tree.get(cur).next.containsKey(c)) {
last = tree.get(cur).next.get(c);
tree.get(last).occurrences++;
return last;
}
// 步骤3：创建新状态
int newState = tree.size();
tree.add(new Node(tree.get(cur).length + 2));
tree.get(cur).next.put(c, newState);
tree.get(newState).occurrences = 1;
// 步骤4：计算新状态的 suffixLink
if (tree.get(newState).length == 1) {
// 长度为1的回文串，suffixLink指向奇根
tree.get(newState).suffixLink = ODD_ROOT;
} else {
// 否则继续跳转找到最长真回文后缀
int link = tree.get(cur).suffixLink;
while (true) {
int linkLen = tree.get(link).length;
if (size - 1 - linkLen - 1 >= 0 && s.charAt(size - 1 - linkLen - 1) == c) {
break;
}
link = tree.get(link).suffixLink;
}
tree.get(newState).suffixLink = tree.get(link).next.get(c);
}
last = newState;
return newState;
}
/**
* 构建回文自动机（处理整个字符串）
*/
public void build(String str) {
for (char c : str.toCharArray()) {
addChar(c);
}
}
/**
* 传播出现次数：从长到短传播 occurrences
* 调用后，每个状态的 occurrences 表示该回文串在字符串中的实际出现次数
*/
public void propagateOccurrences() {
// 按长度从大到小排序状态
List<Integer> states = new ArrayList<>();
for (int i = 2; i < tree.size(); i++) {
states.add(i);
}
states.sort((a, b) -> Integer.compare(tree.get(b).length, tree.get(a).length));
// 传播：长回文串的出现次数贡献给其 suffixLink
for (int state : states) {
int link = tree.get(state).suffixLink;
if (link >= 2) { // 不传播给根节点
tree.get(link).occurrences += tree.get(state).occurrences;
}
}
}
/**
* 获取所有不同回文子串的长度列表
*/
public List<Integer> getAllPalindromeLengths() {
List<Integer> lengths = new ArrayList<>();
for (int i = 2; i < tree.size(); i++) {
lengths.add(tree.get(i).length);
}
return lengths;
}
/**
* 获取最长回文子串的长度
*/
public int getLongestPalindromeLength() {
int maxLen = 0;
for (int i = 2; i < tree.size(); i++) {
maxLen = Math.max(maxLen, tree.get(i).length);
}
return maxLen;
}
/**
* 获取出现次数最多的回文子串信息
*/
public String getMostFrequentPalindrome() {
propagateOccurrences();
long maxOcc = 0;
int maxState = -1;
for (int i = 2; i < tree.size(); i++) {
if (tree.get(i).occurrences > maxOcc) {
maxOcc = tree.get(i).occurrences;
maxState = i;
}
}
if (maxState == -1) return "None";
return "Length=" + tree.get(maxState).length + ", Occurrences=" + maxOcc;
}
/**
* 打印自动机结构（用于调试）
*/
public void printStructure() {
System.out.println("=== Palindromic Tree Structure ===");
System.out.println("Total states (including roots): " + tree.size());
System.out.println("Distinct palindromes: " + distinctPalindromeCount());
for (int i = 0; i < tree.size(); i++) {
Node node = tree.get(i);
System.out.println("State " + i + ": length=" + node.length +
", suffixLink=" + node.suffixLink +
", occurrences=" + node.occurrences +
", next=" + node.next.keySet());
}
}
/**
* 重建某个状态对应的回文串（用于展示）
*/
public String reconstructPalindrome(int state) {
if (state < 2) return state == EVEN_ROOT ? "" : "(odd root)";
// 使用BFS/回溯找到一条从根到该状态的路径
// 这里简化为：从原始字符串中提取
int len = tree.get(state).length;
// 遍历所有可能的起始位置，找到长度为len的回文串
for (int i = 0; i <= s.length() - len; i++) {
if (isPalindrome(s, i, i + len - 1)) {
return s.substring(i, i + len);
}
}
return "Unknown";
}
private boolean isPalindrome(String str, int left, int right) {
while (left < right) {
if (str.charAt(left) != str.charAt(right)) return false;
left++;
right--;
}
return true;
}
// ==================== 应用示例 ====================
/**
* 示例1：统计不同回文子串数量
*/
public static void demoCountDistinct() {
System.out.println("=== Demo 1: Count Distinct Palindromes ===");
String[] testCases = {"abba", "abcba", "aaaa", "abacaba", "leetcode"};
for (String str : testCases) {
PalindromicTree pt = new PalindromicTree();
pt.build(str);
System.out.println("String: \"" + str + "\" -> Distinct palindromes: " +
pt.distinctPalindromeCount());
}
}
/**
* 示例2：查询最长回文后缀
*/
public static void demoLongestPalindromicSuffix() {
System.out.println("\n=== Demo 2: Longest Palindromic Suffix ===");
String str = "abacaba";
PalindromicTree pt = new PalindromicTree();
pt.build(str);
System.out.println("String: \"" + str + "\"");
System.out.println("Longest palindromic suffix length: " +
pt.getLength(pt.getLast()));
}
/**
* 示例3：统计每个回文串的出现次数
*/
public static void demoOccurrences() {
System.out.println("\n=== Demo 3: Palindrome Occurrences ===");
String str = "abacaba";
PalindromicTree pt = new PalindromicTree();
pt.build(str);
pt.propagateOccurrences();
System.out.println("String: \"" + str + "\"");
System.out.println("Palindrome statistics:");
for (int i = 2; i < pt.getNodeCount(); i++) {
System.out.println(" Length " + pt.getLength(i) +
": occurrences=" + pt.tree.get(i).occurrences);
}
}
public static void main(String[] args) {
demoCountDistinct();
demoLongestPalindromicSuffix();
demoOccurrences();
// 完整结构展示
System.out.println("\n=== Full Structure for 'abba' ===");
PalindromicTree pt = new PalindromicTree();
pt.build("abba");
pt.printStructure();
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建自动机 | O(n) | O(n) |
| 添加单个字符 | 均摊 O(1) | O(1) |
| 统计不同回文串 | O(1) | O(1) |
| 传播出现次数 | O(n) | O(n) |
| 查询最长回文后缀 | O(1) | O(1) |
回文自动机的时间复杂度分析关键在于：每个状态最多被创建一次，而 suffixLink 的跳转总次数为 O(n)，因为每次跳转都会减少当前考虑的回文串长度。
回文自动机 vs 其他回文算法
| 算法 | 时间复杂度 | 空间复杂度 | 功能 |
|---|---|---|---|
| 暴力枚举 | O(n³) | O(1) | 判断是否为回文 |
| 中心扩展 | O(n²) | O(1) | 找最长回文子串 |
| Manacher | O(n) | O(n) | 找最长回文子串 |
| 回文自动机 | O(n) | O(n) | 统计所有不同回文串 |
Manacher 算法适合找最长回文子串，而回文自动机更适合统计和查询所有不同的回文子串信息。
应用场景
回文自动机在以下场景中表现出色：
- 回文子串计数：快速统计字符串中不同回文子串的数量
- 回文串频率分析：统计每个回文串出现的次数
- 动态回文查询：在字符流中实时维护回文信息
- 回文串压缩：利用回文结构进行字符串压缩
- 生物信息学：DNA序列中的回文结构分析
总结
回文自动机通过精妙的双根设计和增量构建策略，在 O(n) 时间内完成对所有不同回文子串的统计。每个状态对应一个唯一的回文串，suffixLink 形成了回文串之间的层次结构。掌握回文自动机，将帮助你在字符串回文问题中写出既高效又优雅的解决方案。
