參考資料：Palindromic Tree——回文樹【處理一類回文串問題的強力工具】（請注意，其中似乎有一些錯誤）

回文自動機似乎和回文樹是同一個東西qwq？

回文自動機（PAM）是一種處理回文串的工具。它的每個結(jié)點表示一個本質(zhì)不同的回文串，轉(zhuǎn)移邊\(c\)表示在當前字符串的首尾分別加一個字符\(c\)。

回文自動機由兩棵樹組成，根結(jié)點分別稱為\(odd\)和\(even\)。\(even\)表示空串，長度為\(0\)，長度為偶數(shù)的回文串在它的子樹上；\(odd\)表示一個“虛擬”的串，長度為\(-1\)，長度為奇數(shù)的回文串在它的子樹上。\(odd\)的直接兒子表示只有一個字母的回文串。沿著轉(zhuǎn)移邊\(c\)走一步就在當前串首尾各加上一個字符\(c\)。和AC自動機類似，一個結(jié)點的\(fail\)指針指向它的最長回文真后綴（定義\(fail[even]=odd\)）。比如wqwqqwqwq的回文自動機長這樣（數(shù)字表示結(jié)點編號，紅箭頭表示\(fail\)指針）：

我畫著畫著發(fā)現(xiàn)這個字符串里回文串比想象的多

和后綴自動機類似，構(gòu)造回文自動機也采用每次插入一個字符的方法。設原串是\(S\)，當前位置是\(pos\)，要加入的字符是\(c\)，則可能會多一些以字符\(c\)結(jié)尾的回文串。而多的這些字符串可以看成是一個回文串\([a,pos-1]\)滿足\(S_{a-1}=c\)后面加一個字符\(c\)。于是要找到最長的這樣的回文串\([a,pos-1]\)，即從\(pos-1\)這個結(jié)點開始爬\(fail\)鏈，直到\(p\)點滿足\(S_{pos-len[p]-1}=S_{pos}\)。爬\(fail\)鏈最終會到長度為\(-1\)的\(even\)，由于\(pos-(-1)-1=pos\)，所以這個式子最終一定會成立。這個過程即代碼中的\(get\_fail\)函數(shù)。

設第一個滿足如上條件的點是\(p\)。如果\(p\)已經(jīng)有了\(c\)字符的轉(zhuǎn)移，則直接增加它的\(cnt\)（該字符串出現(xiàn)次數(shù)）即可；如果沒有，則新建結(jié)點\(q\)，\(q\)的長度顯然是\(p\)的長度加\(2\)，\(q\)的\(fail\)是從\(p\)的\(fail\)往上爬，找到第一個在后面加字符\(c\)仍為回文串的地方（方法同上述\(get\_fail\)），把它加字符\(c\)后轉(zhuǎn)移到的點作為\(q\)的\(fail\)。

注意，如果要統(tǒng)計每個回文串的出現(xiàn)次數(shù)（即\(cnt\)），建完后要在\(fail\)樹上做一遍樹上遞推（因為插入的時候只在當前點結(jié)尾的最長回文串的結(jié)點\(cnt\)上加\(1\)。如果一個串出現(xiàn)了，它的最長回文真后綴一定也出現(xiàn)了）。由于回文自動機是兩棵樹，所以不需要像后綴自動機求\(Right\)集合大小一樣拓撲排序，只要按標號從大到小做即可。

題目：洛谷3649

把每個結(jié)點的長度\(len\)乘上出現(xiàn)次數(shù)\(cnt\)然后加起來就好了。

代碼：

#include <cstdio> #include <algorithm> #include <cctype> #include <cstring> #include <string> #define _ 0 using namespace std;namespace zyt {const int N = 3e5 + 10;template<typename T>inline bool read(T &x){char c;bool f = false;x = 0;doc = getchar();while (c != EOF && c != '-' && !isdigit(c));if (c == EOF)return false;if (c == '-')f = true, c = getchar();doc = getchar();while (isdigit(c));if (f)x = -x;return true;}inline bool read(string &s){static char buf[N];if (scanf("%s", buf) == -1)return false;else{s = buf;return true;}}template<typename T>inline void write(T x){static char buf[20];char *pos = buf;if (x < 0)putchar('-'), x = -x;do*pos++ = x % 10 + '0';while (x /= 10);while (pos > buf)putchar(*--pos);}const int CH = 26;typedef long long ll;string s;namespace Palindrome_Auto_Machine{struct node{int len, cnt, fail, s[CH];}tree[N];int cnt, last, odd, even, pos;char s[N];void init(){last = even = 0, odd = 1, cnt = 1, pos = 0;s[0] = '#';tree[odd].len = -1, tree[even].len = 0;tree[odd].fail = tree[even].fail = odd;}int get_fail(int p){while (s[pos - tree[p].len - 1] != s[pos])p = tree[p].fail;return p;}void insert(const char c){s[++pos] = c;int x = c - 'a', p = get_fail(last);if (!tree[p].s[x]){tree[++cnt].len = tree[p].len + 2;tree[cnt].fail = tree[get_fail(tree[p].fail)].s[x];tree[p].s[x] = cnt;}last = tree[p].s[x];++tree[last].cnt;}void build(const string &str){for (int i = 0; i < str.size(); i++)insert(str[i]);for (int i = cnt; i > 0; i--)tree[tree[i].fail].cnt += tree[i].cnt;}inline ll solve(){ll ans = 0;for (int i = 0; i <= cnt; i++)ans = max(ans, (ll)tree[i].cnt * tree[i].len);return ans;}}int work(){using Palindrome_Auto_Machine::init;using Palindrome_Auto_Machine::build;using Palindrome_Auto_Machine::solve;read(s);init();build(s);write(solve());return (0^_^0);} } int main() {return zyt::work(); }

轉(zhuǎn)載于:https://www.cnblogs.com/zyt1253679098/p/10324742.html

總結(jié)

以上是生活随笔為你收集整理的【知识总结】回文自动机（Palindrome_Automaton）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。