C++ 回文自动机（PAM）：原理、实现与应用

2.2 核心初始化函数

初始化回文自动机的两个根节点（偶根、奇根），并设置初始状态：

// 初始化回文自动机
void init_pam() {
    pam.clear();
    // 创建偶根（0 号）和奇根（1 号）
    pam.emplace_back(); // 0: 偶根，len=0
    pam.emplace_back(); // 1: 奇根，len=-1
    pam[0].fail = 1;    // 偶根的失败指针指向奇根
    pam[1].len = -1;    // 奇根长度为 -1
    last = 0;           // 初始 last 指向偶根
    size = 2;           // 初始节点数为 2
}

2.3 核心辅助函数：查找回文后缀

给定当前节点 cur 和字符索引 i，查找能以 s[i] 为结尾的最长回文子串对应的节点（核心！）：

// 查找：从 cur 出发，找到满足 s[i - len[cur] - 1] == s[i] 的节点
int find(int cur, int i) {
    // 回退：直到找到满足条件的节点，或到奇根
    while (i - pam[cur].len - 1 < 0 || s[i - pam[cur].len - 1] != s[i]) {
        cur = pam[cur].fail;
    }
    return cur;
}

三、回文自动机的构建流程（核心实现）

回文自动机的构建是'增量式'的：遍历字符串每个字符，逐步扩展回文子串，核心步骤为「查找→创建节点→设置失败指针→更新转移→更新 last」。

3.1 完整构建函数

// 向回文自动机中添加字符 s[i]
void add_char(int i) {
    char c = s[i];
    int idx = c - 'a';
    // 步骤 1：查找能以 s[i] 结尾的最长回文子串的前驱节点
    int cur = find(last, i);
    // 步骤 2：检查转移是否存在，不存在则创建新节点
    if (pam[cur].trans[idx] == -1) {
        // 2.1 创建新节点
        pam.emplace_back();
        int new_node = size++;
        pam[new_node].len = pam[cur].len + 2; // 回文子串长度 +2（首尾加字符）
        // 2.2 设置新节点的失败指针
        if (pam[new_node].len == 1) {
            // 长度为 1 的回文子串（单个字符），失败指针指向奇根
            pam[new_node].fail = 1;
        } else {
            // 查找失败指针的前驱节点，再取转移
            int fail_cur = find(pam[cur].fail, i);
            pam[new_node].fail = pam[fail_cur].trans[idx];
        }
        // 2.3 更新转移表
        pam[cur].trans[idx] = new_node;
    }
    // 步骤 3：更新 last 为当前字符结尾的最长回文子串节点
    last = pam[cur].trans[idx];
    // 步骤 4：统计出现次数（可选，最后需反向更新）
    pam[last].cnt++;
}

// 构建整个字符串的回文自动机
void build_pam(const string& input) {
    s = input;
    init_pam();
    for (int i = 0; i < s.size(); ++i) {
        add_char(i);
    }
    // 反向更新 cnt：统计每个回文子串的真实出现次数（失败指针的 cnt 累加到当前节点）
    for (int i = size - 1; i >= 2; --i) {
        if (pam[i].fail != -1) {
            pam[pam[i].fail].cnt += pam[i].cnt;
        }
    }
}

3.2 完整测试代码

// 打印所有本质不同的回文子串及其出现次数
void print_palindromes() {
    cout << "本质不同的回文子串：" << endl;
    // 跳过前两个根节点（0：偶根，1：奇根）
    for (int i = 2; i < size; ++i) {
        cout << "长度：" << pam[i].len << "，出现次数：" << pam[i].cnt << endl;
    }
}

// 查找最长回文子串
int find_longest_palindrome() {
    int max_len = 0;
    for (int i = 2; i < size; ++i) {
        max_len = max(max_len, pam[i].len);
    }
    return max_len;
}

// 统计所有回文子串的总数（包括重复）
long long count_all_palindromes() {
    long long total = 0;
    for (int i = 2; i < size; ++i) {
        total += pam[i].cnt;
    }
    return total;
}

int main() {
    string input = "abba";
    build_pam(input);
    cout << "输入字符串：" << input << endl;
    cout << "最长回文子串长度：" << find_longest_palindrome() << endl; // 4
    cout << "本质不同的回文子串数量：" << size - 2 << endl; // 4（a、b、bb、abba）
    cout << "所有回文子串总数：" << count_all_palindromes() << endl; // 5（a:1, b:2, bb:1, abba:1 → 总计 5）
    print_palindromes();
    return 0;
}

输出结果：

输入字符串：abba 
最长回文子串长度：4 
本质不同的回文子串数量：4 
所有回文子串总数：5 
本质不同的回文子串： 
长度：1，出现次数：1 
长度：1，出现次数：2 
长度：2，出现次数：1 
长度：4，出现次数：1 

四、回文自动机的核心应用

4.1 应用 1：统计本质不同的回文子串数量

本质不同的回文子串数量 = 回文自动机的节点数 - 2（减去两个根节点）：

int count_distinct_palindromes() {
    return size - 2;
}

4.2 应用 2：统计所有回文子串的总数（包括重复）

通过 cnt 字段累加即可（需先反向更新 cnt）：

long long count_total_palindromes() {
    long long total = 0;
    for (int i = 2; i < size; ++i) {
        total += pam[i].cnt;
    }
    return total;
}

4.3 应用 3：查找最长回文子串

遍历所有节点，找到 len 最大的节点：

string find_longest_palindrome_str() {
    int max_len = 0;
    int max_node = -1;
    for (int i = 2; i < size; ++i) {
        if (pam[i].len > max_len) {
            max_len = pam[i].len;
            max_node = i;
        }
    }
    // 反向查找最长回文子串的起始位置（可选）
    if (max_len == 0) return "";
    // 简化：直接遍历字符串找最长回文子串（也可通过 PAM 的节点回溯）
    for (int i = 0; i <= s.size() - max_len; ++i) {
        string sub = s.substr(i, max_len);
        // 验证是否为回文
        bool is_pali = true;
        for (int j = 0; j < max_len / 2; ++j) {
            if (sub[j] != sub[max_len - 1 - j]) {
                is_pali = false;
                break;
            }
        }
        if (is_pali) return sub;
    }
    return "";
}

4.4 应用 4：统计各长度回文子串的出现次数

vector<int> count_palindrome_by_len(int max_len) {
    vector<int> res(max_len + 1, 0);
    for (int i = 2; i < size; ++i) {
        int len = pam[i].len;
        if (len <= max_len) {
            res[len] += pam[i].cnt;
        }
    }
    return res;
}
// 测试：count_palindrome_by_len(4) → [0,3,1,0,1]（长度 1：3 次，长度 2：1 次，长度 4：1 次）

4.5 应用 5：判断字符串是否为回文（简化场景）

bool is_palindrome(const string& input) {
    build_pam(input);
    int max_len = find_longest_palindrome();
    return max_len == input.size();
}

五、回文自动机的优化与注意事项

5.1 优化技巧

1. 字符集扩展：若需处理大写字母、数字、中文等，将 trans[26] 改为 unordered_map<char, int>；
2. 内存优化：预先 reserve 节点数组空间（如 pam.reserve(n + 2)），避免频繁扩容；
3. 效率优化：将全局变量封装为类，减少全局变量的访问开销；
4. cnt 统计优化：若仅需统计本质不同的回文子串数量，可省略 cnt 字段和反向更新步骤。

5.2 常见错误

1. 根节点初始化错误：偶根的 fail 未指向奇根，或奇根的 len 未设为 -1，导致查找失败指针时死循环；
2. find 函数边界错误：未检查 i - pam[cur].len - 1 < 0，导致字符串越界访问；
3. cnt 未反向更新：直接使用 cnt 字段统计出现次数，结果偏小（失败指针的 cnt 未累加）；
4. last 未更新：添加字符后未更新 last，导致后续查找错误。

5.3 PAM 与其他回文算法的对比

选择建议：

• 仅找最长回文子串：优先用 Manacher 算法（实现简单）；
• 统计回文子串数量/出现次数：优先用回文自动机；
• 简单场景（短字符串）：用中心扩展法。

六、封装为类的工业级实现

将全局变量封装为类，提升代码的可维护性和复用性：

class PalindromeAutomaton {
private:
    struct Node {
        int trans[26];
        int fail;
        int len;
        int cnt;
        Node() {
            memset(trans, -1, sizeof(trans));
            fail = -1;
            len = 0;
            cnt = 0;
        }
    };
    vector<Node> nodes;
    string s;
    int last;
    int size;

    // 查找辅助函数
    int find(int cur, int i) {
        while (i - nodes[cur].len - 1 < 0 || s[i - nodes[cur].len - 1] != s[i]) {
            cur = nodes[cur].fail;
        }
        return cur;
    }

    // 初始化
    void init() {
        nodes.clear();
        nodes.emplace_back(); // 0: 偶根
        nodes.emplace_back(); // 1: 奇根
        nodes[0].fail = 1;
        nodes[1].len = -1;
        last = 0;
        size = 2;
    }

public:
    PalindromeAutomaton() = default;

    // 构建回文自动机
    void build(const string& input) {
        s = input;
        init();
        for (int i = 0; i < s.size(); ++i) {
            add(i);
        }
        // 反向更新 cnt
        for (int i = size - 1; i >= 2; --i) {
            if (nodes[i].fail != -1) {
                nodes[nodes[i].fail].cnt += nodes[i].cnt;
            }
        }
    }

    // 添加单个字符
    void add(int i) {
        char c = s[i];
        int idx = c - 'a';
        int cur = find(last, i);
        if (nodes[cur].trans[idx] == -1) {
            nodes.emplace_back();
            int new_node = size++;
            nodes[new_node].len = nodes[cur].len + 2;
            if (nodes[new_node].len == 1) {
                nodes[new_node].fail = 1;
            } else {
                int fail_cur = find(nodes[cur].fail, i);
                nodes[new_node].fail = nodes[fail_cur].trans[idx];
            }
            nodes[cur].trans[idx] = new_node;
        }
        last = nodes[cur].trans[idx];
        nodes[last].cnt++;
    }

    // 统计本质不同的回文子串数量
    int count_distinct() {
        return size - 2;
    }

    // 统计所有回文子串总数
    long long count_total() {
        long long total = 0;
        for (int i = 2; i < size; ++i) {
            total += nodes[i].cnt;
        }
        return total;
    }

    // 查找最长回文子串长度
    int longest_palindrome_len() {
        int max_len = 0;
        for (int i = 2; i < size; ++i) {
            max_len = max(max_len, nodes[i].len);
        }
        return max_len;
    }
};

// 测试类实现
int main() {
    PalindromeAutomaton pam;
    pam.build("abba");
    cout << "本质不同的回文子串数：" << pam.count_distinct() << endl; // 4
    cout << "所有回文子串总数：" << pam.count_total() << endl; // 5
    cout << "最长回文子串长度：" << pam.longest_palindrome_len() << endl; // 4
    return 0;
}

七、总结

回文自动机是处理回文子串问题的'专属神器'，核心要点可总结为：

1. 核心思想：利用回文的'首尾扩展'性质，通过失败指针快速回退到最长后缀回文子串，线性时间构建；
2. 核心结构：两个根节点（偶根/奇根）+ 节点（len/fail/trans/cnt）+ last 指针，缺一不可；
3. 核心流程：查找前驱节点 → 创建新节点 → 设置失败指针 → 更新转移 → 更新 last；
4. 核心优势：线性时间/空间，可统计所有回文子串的信息（数量、出现次数、最长长度等）；
5. 应用场景：回文子串统计、最长回文子串、回文子串计数、回文相关竞赛题等。

掌握回文自动机的关键：

• 理解失败指针的作用（快速回退最长后缀回文子串，是 PAM 的灵魂）；
• 牢记 find 函数的逻辑（核心查找步骤，避免越界）；
• 区分'本质不同的回文子串'和'所有回文子串'的统计方式。

回文自动机是 C++ 算法竞赛中处理回文问题的必考知识点，其设计思想（增量构建、失败指针）与 AC 自动机、后缀自动机一脉相承，理解它能帮助你更系统地掌握字符串数据结构体系。