回文自动机 (Palindromic Automaton) 模板详解

靖2025-01-072025-01-07

回文自动机 (Palindromic Automaton) 模板详解

1. 简介

回文自动机（PAM，也称回文树）是一种用于处理字符串中回文子串的高效数据结构。它可以在线性时间内维护字符串中的所有回文子串信息。

主要特点：

线性时间复杂度
在线处理字符串
维护所有回文子串
支持动态添加字符

2. 实现原理

2.1 基本概念

节点结构：
- 表示一个回文子串
- 包含长度、后缀链接等信息
后缀链接：
- 指向最长的回文后缀
- 用于快速转移状态

2.2 核心策略

状态转移：
- 利用后缀链接找到匹配位置
- 维护回文子串的计数
节点维护：
- 两个初始节点（空串和长度为-1的辅助节点）
- 动态添加新的回文节点

3. 模板代码

struct PAM {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        int cnt;
        std::array<int, ALPHABET_SIZE> next;
        Node() : len{}, link{}, cnt{}, next{} {}
    };
    std::vector<Node> t;
    int suff;
    std::string s;
    PAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].len = -1;
        suff = 1;
        s.clear();
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
     
    bool add(char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int let = c - offset;
        int cur = suff, curlen = 0;
 
        while (true) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                break;
            }
            cur = t[cur].link;
        }       
        if (t[cur].next[let]) {  
            suff = t[cur].next[let];
            return false;
        }
         
        int num = newNode();
        suff = num;
        t[num].len = t[cur].len + 2;
        t[cur].next[let] = num;
 
        if (t[num].len == 1) {
            t[num].link = 1;
            t[num].cnt = 1;
            return true;
        }
 
        while (true) {
            cur = t[cur].link;
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[num].link = t[cur].next[let];
                break;
            }       
        }           
 
        t[num].cnt = 1 + t[t[num].link].cnt;
 
        return true;
    }
};

4. 函数说明

4.1 结构体说明

struct Node {
    int len;    // 回文串长度
    int link;   // 后缀链接
    int cnt;    // 出现次数
    std::array<int, ALPHABET_SIZE> next;  // 转移数组
};

4.2 主要函数

init(): 初始化自动机
newNode(): 创建新节点
add(): 添加字符并更新自动机

5. 时间复杂度分析

初始化：O(1)
添加字符：均摊 O(1)
空间复杂度：O(n)，n 为字符串长度

6. 应用场景

统计不同回文子串个数
计算回文子串出现次数
动态维护回文信息
回文串相关问题求解

7. 使用示例

7.1 统计不同回文子串个数

PAM pam;
string s = "ababa";
int count = 0;
for (char c : s) {
    if (pam.add(c)) {
        count++;  // 每当添加新节点时计数
    }
}

7.2 计算回文子串出现次数

PAM pam;
string s = "aba";
for (char c : s) {
    pam.add(c);
}
int total = 0;
for (int i = 2; i < pam.t.size(); i++) {
    total += pam.t[i].cnt;  // 累加每个节点的计数
}