回文自动机 / 回文树（PAM，Palindromic Automaton）

What · 是什么

回文自动机（EER Tree / Palindromic Tree / PAM）是一棵『树 + fail 指针』结构，存储给定串的所有本质不同回文子串：每个节点代表一个回文子串，转移边 ch[c] 表示『在该回文串两端各加字符 c』得到的新回文串，fail 指针指向该回文串的最长回文后缀。有两个初始节点：奇根（长度 -1）与偶根（长度 0）。在线增量构造，加入每个字符时沿 fail 跳转找『两端可加该字符』的最长回文后缀，必要时新建节点并求其 fail。由于每加一个字符本质不同回文子串最多增 1，总状态数 O(n)，构造 O(n)。经典应用：本质不同回文子串个数、各回文子串出现次数（拓扑逆序累计）、最小回文划分（配合 dp 与等差数列优化）。

Why · 为什么

How · 实现

伪代码

struct PAM:
    ch[MAXN][26], fail[MAXN], len[MAXN], cnt[MAXN], s[MAXN]
    last = 0; node 计数 = 1  (0=偶根 len0, 1=奇根 len-1)
    fail[0] = 1, fail[1] = 1

    get_fail(x, p):   # 沿 fail 找两端可加 s[p] 的节点
        while p - len[x] - 1 < 0 or s[p] != s[p - len[x] - 1]:
            x = fail[x]
        return x

    add(p, c):
        s[p] = c
        cur = get_fail(last, p)
        if not ch[cur][c]:
            new = 新建节点; len[new] = len[cur] + 2
            fail[new] = ch[get_fail(fail[cur], p)][c]
            if fail[new] == new: fail[new] = 0
            ch[cur][c] = new
        last = ch[cur][c]
        cnt[last] += 1

    build(): for i in 0..n-1: add(i, s[i])
    出现次数: for i 逆序: cnt[fail[i]] += cnt[i]

Python 实现

class PAM:
    def __init__(self, n):
        self.maxn = n + 3
        self.ch = [[0] * 26 for _ in range(self.maxn)]
        self.fail = [0] * self.maxn
        self.len = [0] * self.maxn
        self.cnt = [0] * self.maxn
        self.s = [''] * self.maxn
        self.cur_node = 2  # 0=偶根, 1=奇根, 新节点从 2 起
        self.last = 0
        self.sz = 0  # 已处理字符数
        self.len[0] = 0
        self.len[1] = -1
        self.fail[0] = 1
        self.fail[1] = 1

    def get_fail(self, x, p):
        while True:
            curlen = self.len[x]
            if p - curlen - 1 >= 0 and self.s[p] == self.s[p - curlen - 1]:
                return x
            x = self.fail[x]

    def add(self, c):
        p = self.sz
        self.s[p] = c
        self.sz += 1
        code = ord(c) - ord('a')
        cur = self.get_fail(self.last, p)
        if self.ch[cur][code] == 0:
            nxt = self.cur_node
            self.cur_node += 1
            self.len[nxt] = self.len[cur] + 2
            f = self.get_fail(self.fail[cur], p)
            self.fail[nxt] = self.ch[f][code]
            if self.fail[nxt] == nxt:
                self.fail[nxt] = 0
            self.ch[cur][code] = nxt
        self.last = self.ch[cur][code]
        self.cnt[self.last] += 1

    def build(self, s):
        for c in s:
            self.add(c)

    def distinct_palindromes(self):
        return self.cur_node - 2

    def occurrence(self):
        """返回各节点代表的回文子串出现次数（按节点编号）"""
        for i in range(self.cur_node - 1, 1, -1):
            self.cnt[self.fail[i]] += self.cnt[i]
        return self.cnt[:self.cur_node]

if __name__ == '__main__':
    s = 'abacababbab'
    pam = PAM(len(s))
    pam.build(s)
    print('distinct palindromes =', pam.distinct_palindromes())
    occ = pam.occurrence()
    # 验证：手工枚举本质不同回文子串个数
    pal = set()
    n = len(s)
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j + 1]
            if sub == sub[::-1]:
                pal.add(sub)
    assert pam.distinct_palindromes() == len(pal), (pam.distinct_palindromes(), len(pal))
    print('distinct count matches brute force:', len(pal))
    # 出现次数抽样验证：枚举所有回文子串，逐串在 PAM 中匹配并核对次数
    from collections import Counter
    brute = Counter()
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j + 1]
            if sub == sub[::-1]:
                brute[sub] += 1
    # 通过两端扩展在 PAM 上定位节点（fail 链寻址）
    def node_of(pal):
        if pal == '':
            return 0
        if len(pal) == 1:
            return pam.ch[1][ord(pal) - ord('a')]
        inner = pal[1:-1]
        nid = node_of(inner)
        return pam.ch[nid][ord(pal[0]) - ord('a')]
    checked = 0
    for pal_s, c in brute.items():
        occ_id = node_of(pal_s)
        assert occ[occ_id] == c, (pal_s, occ[occ_id], c)
        checked += 1
    assert checked == len(brute) == len(pal)
    print('occurrence counts verified for %d distinct palindromes' % checked)
    print('OK')

易错点

• 奇根 len=-1 的意义与 fail 初值（fail[0]=fail[1]=1）缺一不可，否则单字符失配处理错误
• 新建节点 fail 的求取必须从 fail[cur] 出发而非 cur，否则得到自身或错链
• get_fail 的边界条件 p-len[x]-1<0 必须先判，防止负下标访问哨兵前
• cnt 只在 add 时 +1，出现次数必须在全部添加完后逆序累加到 fail
• ch 表大小 = n+3（含奇偶根），开小会越界；多组数据需重置 0/1 根
• 最小回文划分的 dp 方向与 slink 前缀和 g 数组需与节点顺序一致

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/string/pam.md
• OI Wiki✓ https://oi-wiki.org/string/pam/