算法

回文自动机其实挺简单的，我就尽量简 (tou) 单 (lan) 地讲了

首先回文自动机是用来维护一个字符串的所有回文子串的

回文自动机的每个节点代表一种回文子串

例如 abcaaa 中就有如下节点：

a, b, c, aa, aaa

也就是出现位置不同但本质相同的回文子串会被归在一个节点内

然后类似于 AC 自动机之类的，$next[i][c]$表示在 $i$节点所代表的回文子串的首尾都添加一个字符 $c$得到的回文子串所在的节点，如果新的回文串不存在于原串中则 $next[i][c] = \mathrm {null}$

以 $next$为边会让整个回文自动机构成树形结构，并且一定是两棵树：一颗树中的回文串长度都是奇数，另一颗都是偶数 （然而两棵都一定是枣树），它们之间是没有 $next$边相连的

如果你已经构建出了两棵树，那你就能判断某个回文串是否是原串的子串啦！

那怎么构建出这两棵树呢？

我们定义 $fail[i]$表示 $i$节点所代表的回文串的最长回文后缀所在的节点

比如上面举的例子：

abcaaa

a, b, c, aa, aaa

假如 aaa 的节点编号为 5，aa 的节点编号为 4，那么 $fail[5] = 4$，即 aa 是 aaa 的最长回文后缀

再假如 a 的节点编号为 1 则 $fail[4] = 1$，即 a 是 aa 的最长回文后缀

假设我们已经构建出了原串的前 $i – 1$个字符构成的回文自动机，现在要加入第 $i$个字符 $c$

设 $last$为最后插入的节点

由于插入的字符在最后面，所以新增的回文子串一定是以 $i$结尾的，它们一定是由以 $i – 1$结尾的回文子串在首尾添加字符 $c$得来的

因此就顺着 $last$的 $fail$链向上跳，直到找到某个以 $i – 1$结尾的回文子串在首尾添加字符 $c$得到的依然是一个回文子串，设这个以 $i – 1$结尾的回文子串所在的节点为 $p$

那么 $next[p][c]$就是新插入的节点，它代表的是以 $i$结尾的最长回文子串

那新建的节点的 $fail$怎么找呢？只要沿着 $p$的 $fail$链继续向上跳找到第二个首尾添加字符 $c$为回文串的节点 $q$，把 $fail$设成 $next[q][c]$就行了

过程中如果某个节点不存在的话就让它一直跳到根节点就行了

根节点有两个，分别代表长度为奇数的和长度为偶数的

把两个根的 $fail$都设置为长度为奇数的根，因为单个字符也是回文串，所以长度为奇数的根一定存在可行的转移方案

复杂度是 $O(n)$的，懒得证了_(:зゝ∠)_ 大概和 AC 自动机差不多

还有不懂的直接看代码吧，代码很好写也很好懂的。。。

例题

[Apio2014] 回文串 BZOJ – 3676

建回文自动机的时候统计一下每个点被插入的次数（被插入次数不一定为 1，因为可能某次要插入的节点已经存在了），当然还要保存每个点代表的回文串长度

然后某个点在原串中的出现次数就是它在 $fail$树中的子树插入次数和

代码（代码中的 $pre$就是 $fail$）：

#include <bits/stdc++.h>

#define NS (300005)

using namespace std;

typedef long long LL;

int n;

char s[NS];

LL ans;

struct PAM
{
    int n, nxt[NS][26], pre[NS], len[NS], cnt[NS], sz;
    PAM() { pre[0] = pre[1] = sz = 1, len[1] = -1; }
    void run(char (&s)[NS])
    {
        n = strlen(s + 1);
        for (int i = 1, p = 0; i <= n; i += 1)
        {
            while (s[i - len[p] - 1] != s[i]) p = pre[p];
            if (!nxt[p][s[i] - 'a'])
            {
                int a = ++sz, b = pre[p];
                len[a] = len[p] + 2;
                while (s[i - len[b] - 1] != s[i]) b = pre[b];
                pre[a] = nxt[b][s[i] - 'a'], nxt[p][s[i] - 'a'] = a;
            }
            p = nxt[p][s[i] - 'a'], cnt[p]++;
        }
    }
    void cal()
    {
        for (int i = sz; i > 1; i -= 1)
            cnt[pre[i]] += cnt[i], ans = max(ans, 1ll * len[i] * cnt[i]);
    }
} pam;

int main(int argc, char const* argv[])
{
    scanf("%s", s + 1), pam.run(s), pam.cal(), printf("%lld\n", ans);
    return 0;
}

---

最长双回文串 BZOJ – 2565

把串正着建一个回文自动机反着建一个回文自动机

就能统计以某个位置开头和结尾的回文串的最大长度

代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

struct PAM
{
    int n, nxt[NS][26], pre[NS], len[NS], sz, mx[NS];
    PAM() { pre[0] = pre[1] = sz = 1, len[1] = -1; }
    void run(char (&s)[NS])
    {
        n = strlen(s + 1);
        for (int i = 1, p = 0; i <= n; i += 1)
        {
            while (s[i - len[p] - 1] != s[i]) p = pre[p];
            if (!nxt[p][s[i] - 'a'])
            {
                int a = ++sz, b = pre[p];
                len[a] = len[p] + 2;
                while (s[i - len[b] - 1] != s[i]) b = pre[b];
                pre[a] = nxt[b][s[i] - 'a'], nxt[p][s[i] - 'a'] = a;
            }
            p = nxt[p][s[i] - 'a'], mx[i] = len[p];
        }
    }
} p1, p2;

char s[NS];

int n, ans;

int main(int argc, char const* argv[])
{
    scanf("%s", s + 1), n = strlen(s + 1);
    p1.run(s), reverse(s + 1, s + 1 + n), p2.run(s);
    reverse(p2.mx + 1, p2.mx + 1 + n);
    for (int i = 1; i < n; i += 1) ans = max(ans, p1.mx[i] + p2.mx[i + 1]);
    printf("%d\n", ans);
    return 0;
}