【知识总结】回文自动机（Palindrome_Automaton）

参考资料：Palindromic Tree——回文树【处理一类回文串问题的强力工具】（请注意，其中似乎有一些错误）

回文自动机似乎和回文树是同一个东西qwq？

回文自动机（PAM）是一种处理回文串的工具。它的每个结点表示一个本质不同的回文串，转移边\(c\)表示在当前字符串的首尾分别加一个字符\(c\)。

回文自动机由两棵树组成，根结点分别称为\(odd\)和\(even\)。\(even\)表示空串，长度为\(0\)，长度为偶数的回文串在它的子树上；\(odd\)表示一个“虚拟”的串，长度为\(-1\)，长度为奇数的回文串在它的子树上。\(odd\)的直接儿子表示只有一个字母的回文串。沿着转移边\(c\)走一步就在当前串首尾各加上一个字符\(c\)。和AC自动机类似，一个结点的\(fail\)指针指向它的最长回文真后缀（定义\(fail[even]=odd\)）。比如wqwqqwqwq的回文自动机长这样（数字表示结点编号，红箭头表示\(fail\)指针）：

我画着画着发现这个字符串里回文串比想象的多

和后缀自动机类似，构造回文自动机也采用每次插入一个字符的方法。设原串是\(S\)，当前位置是\(pos\)，要加入的字符是\(c\)，则可能会多一些以字符\(c\)结尾的回文串。而多的这些字符串可以看成是一个回文串\([a,pos-1]\)满足\(S_{a-1}=c\)后面加一个字符\(c\)。于是要找到最长的这样的回文串\([a,pos-1]\)，即从\(pos-1\)这个结点开始爬\(fail\)链，直到\(p\)点满足\(S_{pos-len[p]-1}=S_{pos}\)。爬\(fail\)链最终会到长度为\(-1\)的\(even\)，由于\(pos-(-1)-1=pos\)，所以这个式子最终一定会成立。这个过程即代码中的\(get\_fail\)函数。

设第一个满足如上条件的点是\(p\)。如果\(p\)已经有了\(c\)字符的转移，则直接增加它的\(cnt\)（该字符串出现次数）即可；如果没有，则新建结点\(q\)，\(q\)的长度显然是\(p\)的长度加\(2\)，\(q\)的\(fail\)是从\(p\)的\(fail\)往上爬，找到第一个在后面加字符\(c\)仍为回文串的地方（方法同上述\(get\_fail\)），把它加字符\(c\)后转移到的点作为\(q\)的\(fail\)。

注意，如果要统计每个回文串的出现次数（即\(cnt\)），建完后要在\(fail\)树上做一遍树上递推（因为插入的时候只在当前点结尾的最长回文串的结点\(cnt\)上加\(1\)。如果一个串出现了，它的最长回文真后缀一定也出现了）。由于回文自动机是两棵树，所以不需要像后缀自动机求\(Right\)集合大小一样拓扑排序，只要按标号从大到小做即可。

题目：洛谷3649

把每个结点的长度\(len\)乘上出现次数\(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(); }

转载于:https://www.cnblogs.com/zyt1253679098/p/10324742.html

总结

以上是生活随笔为你收集整理的【知识总结】回文自动机（Palindrome_Automaton）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。