每日算法 — 使用java实现回文树：线性时间处理所有回文子串

引言

回文子串问题在字符串算法中占据重要地位。传统的Manacher算法可以在线性时间内找到最长回文子串，但如果需要枚举所有不同的回文子串、统计回文子串出现次数、或回答关于回文子串的复杂查询，Manacher算法便显得力不从心。回文树（Palindromic Tree，又称Eertree）是Mikhail Rubinchik于2014年提出的一种优雅数据结构，它可以在O(n)时间内构建，并支持O(1)查询任意前缀中不同回文子串的数量。本文将深入讲解回文树的原理与实现。

核心原理

结构定义

回文树由两种节点组成：

1. 奇根（Odd Root）：代表长度为奇数的回文串，其长度为-1（抽象节点，便于边界处理）
2. 偶根（Even Root）：代表长度为偶数的回文串，其长度为0
3. 普通节点：每个节点代表一个不同的回文子串，节点存储该回文串的长度

关键性质

性质1：一个长度为n的字符串最多有n个不同的回文子串。

这意味着回文树的空间复杂度为O(n)。

性质2：每个节点维护一个fail指针，指向该回文串的最长真回文后缀。

fail指针构成了回文树的另一棵树结构，便于快速跳转。

性质3：每个节点维护next边（类似Trie），表示在回文串两侧同时添加某个字符后形成的新回文串。

增量构建

回文树的构建采用在线增量方式。处理字符串s[0...i]时，利用s[0...i-1]的回文树，找到能通过在两端添加s[i]形成的最长回文后缀，然后添加新节点。

具体步骤：
1. 从上一个回文串所在节点出发，沿fail链寻找合适的父节点
2. 检查在父节点代表的回文串两侧添加s[i]是否形成回文
3. 若形成新回文且未存在，则创建新节点
4. 设置新节点的fail指针

Java实现

import java.util.HashMap;
import java.util.Map;

/**
 * 回文树（Eertree / Palindromic Tree）实现
 * 线性时间构建，O(1)查询不同回文子串数量
 */
public class PalindromicTree {

    /**
     * 回文树节点
     */
    private static class Node {
        int length;                    // 该节点代表的回文串长度
        int count;                     // 该回文串出现的次数（需在最后countPropagation）
        int occurrence;                // 该回文串作为后缀出现的次数
        Node suffixLink;               // fail指针：最长真回文后缀
        Map<Character, Node> next;     // 转移边：c -> 在两侧添加c后的回文节点

        Node(int length) {
            this.length = length;
            this.count = 0;
            this.occurrence = 0;
            this.suffixLink = null;
            this.next = new HashMap<>();
        }
    }

    private String s;           // 原始字符串
    private Node root1;         // 奇根，长度-1
    private Node root2;         // 偶根，长度0
    private Node last;          // 指向当前最长回文后缀节点
    private int size;           // 节点总数（不含两个根）

    public PalindromicTree(String s) {
        this.s = s;
        this.size = 0;

        // 初始化两个根节点
        root1 = new Node(-1);   // 奇根
        root2 = new Node(0);    // 偶根
        root1.suffixLink = root1;
        root2.suffixLink = root1;
        last = root2;

        // 逐个字符构建回文树
        for (int i = 0; i < s.length(); i++) {
            addChar(i);
        }

        // 传播occurrence到count（自底向上）
        countPropagation();
    }

    /**
     * 添加第pos个字符，O(1)均摊
     */
    private void addChar(int pos) {
        char c = s.charAt(pos);
        Node cur = last;

        // 沿fail链寻找能在两侧添加s[pos]形成回文的节点
        while (true) {
            int curLen = cur.length;
            // 检查 pos - curLen - 1 位置的字符是否等于 pos 位置的字符
            if (pos - curLen - 1 >= 0 && s.charAt(pos - curLen - 1) == c) {
                break;
            }
            cur = cur.suffixLink;
        }

        // 检查该回文是否已经存在
        if (cur.next.containsKey(c)) {
            last = cur.next.get(c);
            last.occurrence++;
            return;
        }

        // 创建新节点
        Node newNode = new Node(cur.length + 2);
        cur.next.put(c, newNode);
        size++;

        // 设置fail指针
        if (newNode.length == 1) {
            // 长度为1的回文串，fail指向偶根
            newNode.suffixLink = root2;
        } else {
            // 沿父节点的fail链继续寻找
            Node failCur = cur.suffixLink;
            while (true) {
                int failLen = failCur.length;
                if (pos - failLen - 1 >= 0 && s.charAt(pos - failLen - 1) == c) {
                    break;
                }
                failCur = failCur.suffixLink;
            }
            newNode.suffixLink = failCur.next.get(c);
        }

        newNode.occurrence = 1;
        last = newNode;
    }

    /**
     * 传播occurrence：每个节点的count应包含其所有后缀回文的出现次数
     * 按长度从大到小排序后传播
     */
    private void countPropagation() {
        // 收集所有节点
        java.util.List<Node> nodes = new java.util.ArrayList<>();
        collectNodes(root1, nodes);
        collectNodes(root2, nodes);

        // 按长度从大到小排序
        nodes.sort((a, b) -> b.length - a.length);

        // 传播：每个节点的出现次数加到其fail指针指向的节点
        for (Node node : nodes) {
            if (node.suffixLink != null && node != root1 && node != root2) {
                node.suffixLink.count += node.count;
            }
            // 第一次传播时count为0，需要把occurrence加进去
            node.count += node.occurrence;
        }
    }

    private void collectNodes(Node node, java.util.List<Node> nodes) {
        if (node == null) return;
        if (node != root1 && node != root2) {
            nodes.add(node);
        }
        for (Node child : node.next.values()) {
            collectNodes(child, nodes);
        }
    }

    /**
     * 获取不同回文子串的数量
     */
    public int distinctPalindromeCount() {
        return size;
    }

    /**
     * 获取回文子串的总出现次数（含重复）
     */
    public int totalPalindromeOccurrences() {
        int total = 0;
        java.util.List<Node> nodes = new java.util.ArrayList<>();
        collectNodes(root1, nodes);
        collectNodes(root2, nodes);
        for (Node node : nodes) {
            total += node.count;
        }
        return total;
    }

    /**
     * 获取最长回文子串的长度
     */
    public int longestPalindromeLength() {
        int maxLen = 0;
        java.util.List<Node> nodes = new java.util.ArrayList<>();
        collectNodes(root1, nodes);
        collectNodes(root2, nodes);
        for (Node node : nodes) {
            if (node.length > maxLen) {
                maxLen = node.length;
            }
        }
        return maxLen;
    }

    /**
     * 打印所有不同的回文子串及其出现次数
     */
    public void printAllPalindromes() {
        System.out.println("所有不同回文子串（回文树遍历）：");
        System.out.println("节点总数（不含根）: " + size);

        java.util.List<Node> nodes = new java.util.ArrayList<>();
        collectNodes(root1, nodes);
        collectNodes(root2, nodes);

        for (Node node : nodes) {
            System.out.println("长度=" + node.length + ", 出现次数=" + node.count);
        }
    }

    /**
     * 构建回文子串的具体内容（通过长度和位置回溯）
     */
    public void printPalindromeSubstrings() {
        System.out.println("\n具体回文子串内容：");
        java.util.Set<String> seen = new java.util.HashSet<>();

        for (int center = 0; center < s.length(); center++) {
            // 奇数长度回文
            expandAndPrint(center, center, seen);
            // 偶数长度回文
            if (center + 1 < s.length()) {
                expandAndPrint(center, center + 1, seen);
            }
        }
    }

    private void expandAndPrint(int left, int right, java.util.Set<String> seen) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            String pal = s.substring(left, right + 1);
            if (seen.add(pal)) {
                System.out.println("\"" + pal + "\"");
            }
            left--;
            right++;
        }
    }

    /**
     * 检查字符串是否为回文（辅助方法）
     */
    public static boolean isPalindrome(String str) {
        int i = 0, j = str.length() - 1;
        while (i < j) {
            if (str.charAt(i) != str.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
        // 测试用例1
        String s1 = "abbaabba";
        PalindromicTree pt1 = new PalindromicTree(s1);
        System.out.println("字符串: " + s1);
        System.out.println("不同回文子串数量: " + pt1.distinctPalindromeCount());
        System.out.println("最长回文长度: " + pt1.longestPalindromeLength());
        pt1.printAllPalindromes();
        pt1.printPalindromeSubstrings();

        System.out.println("\n==========\n");

        // 测试用例2
        String s2 = "aaaa";
        PalindromicTree pt2 = new PalindromicTree(s2);
        System.out.println("字符串: " + s2);
        System.out.println("不同回文子串数量: " + pt2.distinctPalindromeCount());
        System.out.println("最长回文长度: " + pt2.longestPalindromeLength());
        pt2.printAllPalindromes();

        System.out.println("\n==========\n");

        // 测试用例3
        String s3 = "abcba";
        PalindromicTree pt3 = new PalindromicTree(s3);
        System.out.println("字符串: " + s3);
        System.out.println("不同回文子串数量: " + pt3.distinctPalindromeCount());
        pt3.printAllPalindromes();
    }
}

复杂度分析

时间复杂度

• 构建：O(n)。每个字符处理时，沿fail链跳转的总次数均摊为常数。因为每次跳转都会使当前考虑的回文长度严格减小，而新创建的节点最多n个。
• 查询不同回文数量：O(1)，直接返回节点计数
• 统计出现次数：需要一次拓扑序传播，O(n)

空间复杂度

• O(n)，不同回文子串最多n个，每个节点存储O(1)基本信息和转移边

正确性证明要点

引理：字符串s[0...i]的不同回文后缀数量等于从last节点沿fail链到根的路径上（不含根）的节点数。

证明思路：
1. 每个回文后缀对应回文树上的一个节点
2. fail指针恰好指向最长真回文后缀
3. 因此fail链穷尽了所有回文后缀
4. 不同回文后缀互不相同，故节点数等于回文后缀数

与其他回文算法的对比

应用场景

1. 统计不同回文子串数量：回文树直接给出答案
2. 回文子串出现次数统计：通过occurrence传播实现
3. 回文串自动机：利用类似AC自动机的思想处理回文相关模式匹配
4. 字符串压缩：基于回文结构的压缩算法
5. 生物信息学：DNA序列中的回文结构分析

总结

回文树是字符串算法领域中相对年轻但极为优雅的数据结构。它通过将回文子串组织成一棵树，并巧妙地利用fail指针和字符转移边，实现了在线性时间内处理所有回文信息的目标。与Manacher算法专注于”最长回文”不同，回文树提供了一种全局视角来审视字符串中的回文结构。掌握回文树，不仅能解决复杂的回文查询问题，更能加深对自动机思想和后缀结构的理解。