回文自动机

概念讲解

什么是回文自动机？

回文自动机（PAM，Eertree）是一种用于处理回文串的数据结构。

核心思想

将所有回文串组织成树形结构。

实现

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960const int N = 100005;
const int ALPHABET = 26;

struct PAM {
    int trie[N][ALPHABET];
    int fail[N];
    int len[N];
    int count[N];
    int last;
    int idx;
    char s[N];
    int n;
    
    PAM() {
        init();
    }
    
    void init() {
        memset(trie[0], 0, sizeof(trie[0]));
        memset(trie[1], 0, sizeof(trie[1]));
        len[0] = -1;
        len[1] = 0;
        fail[0] = 1;
        fail[1] = 0;
        last = 1;
        idx = 1;
        n = 0;
        s[0] = -1;
    }
    
    int getFail(int x) {
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }
    
    void extend(char c) {
        s[++n] = c;
        int u = c - 'a';
        int cur = getFail(last);
        
        if (!trie[cur][u]) {
            int v = ++idx;
            memset(trie[v], 0, sizeof(trie[v]));
            len[v] = len[cur] + 2;
            fail[v] = trie[getFail(fail[cur])][u];
            trie[cur][u] = v;
        }
        
        last = trie[cur][u];
        count[last]++;
    }
    
    void build() {
        for (int i = idx; i >= 2; i--) {
            count[fail[i]] += count[i];
        }
    }
};

应用场景

1. 本质不同回文串计数

1234567int countDistinctPalindromes(string s) {
    PAM pam;
    for (char c : s) {
        pam.extend(c);
    }
    return pam.idx - 1;  // 减去两个根节点
}

2. 回文串出现次数

1// count[i] 表示以 i 结尾的回文串出现次数

考点分析

初赛考查方式

  1. 选择题： 回文自动机的概念
  2. 程序阅读： 理解回文自动机
  3. 编程题： 回文自动机应用

常见题型

  • 本质不同回文串计数
  • 回文串出现次数

例题精讲

例题 1：本质不同回文串计数

题目： 求字符串中本质不同的回文子串个数。

解答：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <iostream>
#include <cstring>
using namespace std;

const int N = 100005;
const int ALPHABET = 26;

struct PAM {
    int trie[N][ALPHABET];
    int fail[N];
    int len[N];
    int count[N];
    int last;
    int idx;
    char s[N];
    int n;
    
    PAM() {
        init();
    }
    
    void init() {
        memset(trie[0], 0, sizeof(trie[0]));
        memset(trie[1], 0, sizeof(trie[1]));
        len[0] = -1;
        len[1] = 0;
        fail[0] = 1;
        fail[1] = 0;
        last = 1;
        idx = 1;
        n = 0;
        s[0] = -1;
    }
    
    int getFail(int x) {
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }
    
    void extend(char c) {
        s[++n] = c;
        int u = c - 'a';
        int cur = getFail(last);
        
        if (!trie[cur][u]) {
            int v = ++idx;
            memset(trie[v], 0, sizeof(trie[v]));
            len[v] = len[cur] + 2;
            fail[v] = trie[getFail(fail[cur])][u];
            trie[cur][u] = v;
        }
        
        last = trie[cur][u];
        count[last]++;
    }
};

int main() {
    string s;
    cin >> s;
    
    PAM pam;
    for (char c : s) {
        pam.extend(c);
    }
    
    cout << pam.idx - 1 << endl;
    
    return 0;
}

练习题

  1. 洛谷 P5496 【模板】回文自动机（PAM）
查看答案

思路：回文自动机模板题。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include <iostream>
#include <cstring>
using namespace std;

const int N = 500005;
const int ALPHABET = 26;

struct PAM {
    int trie[N][ALPHABET];
    int fail[N];
    int len[N];
    int count[N];
    int last;
    int idx;
    char s[N];
    int n;
    
    PAM() {
        init();
    }
    
    void init() {
        memset(trie[0], 0, sizeof(trie[0]));
        memset(trie[1], 0, sizeof(trie[1]));
        len[0] = -1;
        len[1] = 0;
        fail[0] = 1;
        fail[1] = 0;
        last = 1;
        idx = 1;
        n = 0;
        s[0] = -1;
    }
    
    int getFail(int x) {
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }
    
    void extend(char c) {
        s[++n] = c;
        int u = c - 'a';
        int cur = getFail(last);
        
        if (!trie[cur][u]) {
            int v = ++idx;
            memset(trie[v], 0, sizeof(trie[v]));
            len[v] = len[cur] + 2;
            fail[v] = trie[getFail(fail[cur])][u];
            trie[cur][u] = v;
        }
        
        last = trie[cur][u];
        count[last]++;
    }
    
    void build() {
        for (int i = idx; i >= 2; i--) {
            count[fail[i]] += count[i];
        }
    }
};

int main() {
    string s;
    cin >> s;
    
    PAM pam;
    int last = 0;
    
    for (char c : s) {
        c = (c - 'a' + last) % 26 + 'a';
        pam.extend(c);
        last = pam.idx - 1;
        cout << last << " ";
    }
    cout << endl;
    
    return 0;
}
  1. 洛谷 P3649 [APIO2014] 回文串
查看答案

思路：回文自动机，统计每个回文串的出现次数。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include <iostream>
#include <cstring>
using namespace std;

const int N = 300005;
const int ALPHABET = 26;

struct PAM {
    int trie[N][ALPHABET];
    int fail[N];
    int len[N];
    int count[N];
    int last;
    int idx;
    char s[N];
    int n;
    
    PAM() {
        init();
    }
    
    void init() {
        memset(trie[0], 0, sizeof(trie[0]));
        memset(trie[1], 0, sizeof(trie[1]));
        len[0] = -1;
        len[1] = 0;
        fail[0] = 1;
        fail[1] = 0;
        last = 1;
        idx = 1;
        n = 0;
        s[0] = -1;
    }
    
    int getFail(int x) {
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }
    
    void extend(char c) {
        s[++n] = c;
        int u = c - 'a';
        int cur = getFail(last);
        
        if (!trie[cur][u]) {
            int v = ++idx;
            memset(trie[v], 0, sizeof(trie[v]));
            len[v] = len[cur] + 2;
            fail[v] = trie[getFail(fail[cur])][u];
            trie[cur][u] = v;
        }
        
        last = trie[cur][u];
        count[last]++;
    }
    
    void build() {
        for (int i = idx; i >= 2; i--) {
            count[fail[i]] += count[i];
        }
    }
};

int main() {
    string s;
    cin >> s;
    
    PAM pam;
    for (char c : s) {
        pam.extend(c);
    }
    pam.build();
    
    long long ans = 0;
    for (int i = 2; i <= pam.idx; i++) {
        ans = max(ans, (long long)pam.len[i] * pam.count[i]);
    }
    
    cout << ans << endl;
    return 0;
}
  1. 洛谷 P4287 [SHOI2011] 双倍回文
查看答案

思路：回文自动机，找双倍回文串。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <iostream>
#include <cstring>
using namespace std;

const int N = 500005;
const int ALPHABET = 26;

struct PAM {
    int trie[N][ALPHABET];
    int fail[N];
    int len[N];
    int count[N];
    int last;
    int idx;
    char s[N];
    int n;
    
    PAM() {
        init();
    }
    
    void init() {
        memset(trie[0], 0, sizeof(trie[0]));
        memset(trie[1], 0, sizeof(trie[1]));
        len[0] = -1;
        len[1] = 0;
        fail[0] = 1;
        fail[1] = 0;
        last = 1;
        idx = 1;
        n = 0;
        s[0] = -1;
    }
    
    int getFail(int x) {
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }
    
    void extend(char c) {
        s[++n] = c;
        int u = c - 'a';
        int cur = getFail(last);
        
        if (!trie[cur][u]) {
            int v = ++idx;
            memset(trie[v], 0, sizeof(trie[v]));
            len[v] = len[cur] + 2;
            fail[v] = trie[getFail(fail[cur])][u];
            trie[cur][u] = v;
        }
        
        last = trie[cur][u];
        count[last]++;
    }
};

int main() {
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    PAM pam;
    for (char c : s) {
        pam.extend(c);
    }
    
    int ans = 0;
    for (int i = 2; i <= pam.idx; i++) {
        if (pam.len[i] % 4 == 0) {
            int half = pam.len[i] / 2;
            int p = pam.fail[i];
            while (p > 1) {
                if (pam.len[p] == half) {
                    ans = max(ans, pam.len[i]);
                    break;
                }
                p = pam.fail[p];
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 回文自动机有两个根节点
  2. fail 指针的构建是关键
  3. 回文自动机是字符串算法的高级内容
  4. 注意数组大小