「笔记」回文自动机

• 写在前面
• 结构
• 构造
• 复杂度证明
• 模板题
• 代码
• 写在最后

写在前面

其实这东西学名叫 EER Tree，Palindromic Tree，直译是回文树，但本质上是一类有限状态自动机所以也可以叫 Palindromic Automaton，因为我很喜欢自动机所以以下都叫它回文自动机。

结构

类似后缀自动机的，回文自动机（以下简称 PAM）也是一类确定有限状态自动机。对于字符串 \(S\)，它的回文自动机是由以下五部分构成的五元组：

• 状态集合 \(Q\)：每个状态对应 \(S\) 中的本质不同的回文子串。
• 字符集 \(\Sigma\)。
• 转移函数\(\delta\)：有：\(Q\times \Sigma \rightarrow Q\)，转移函数 \(\delta(u, c)\) 存在当且仅当在 \(u\) 对应的回文子串两端添加字符 \(c\) 得到的字符串也是 \(S\) 的一个子串。
• 起始状态 \(start\)，代表空串。
• 接受状态集合 \(F\)。

特别地，对于每个状态定义 \(\operatorname{len}\) 表示该状态对应的回文串的长度，定义 \(\operatorname{fail}\) 指针指向该状态对应的回文串的最长的回文后缀。显然 \(\operatorname{fail}\) 指针只会连向长度严格小于当前状态的回文串对应的状态，则由各状态和 \(\operatorname{fail}\) 指针构成了一棵树，称为回文树。

看起来和 SAM 非常像，但需要注意的是回文串存在奇数和偶数长度的，按照上述定义的话转移和 \(\operatorname{fail}\) 均只能转移到与当前状态对应字符串长度奇偶性相同的状态，于是钦定了 PAM 中存在两个代表空串的初始状态，分别代表长度为 -1 和 0 的回文串，可以称它们为奇根，偶根，并且钦定偶根的 \(\operatorname{fail}\) 指针指向奇根，而我们并不关心奇根的 \(\operatorname{fail}\) 指针，因为奇根不可能失配（奇根转移出的下一个状态长度为 1，即单个字符。一定是回文子串）。

另外，PAM 比 SAM 更直观的一点是每个状态仅代表唯一的本质不同的回文子串。

构造

与 SAM 类似地，考虑使用增量法构建 PAM，即在 \(s[1:i-1]\) 的 PAM 基础上构造 \(s[1:i]\) 的 PAM。考虑维护一个 \(\operatorname{last}\) 指针指向 \(s[1:i-1]\) 的最长回文后缀，初始时 \(\operatorname{last}\) 指向偶根。然后对 \(\operatorname{last}\) 不断地跳 \(\operatorname{fail}\)，即按长度递减不断枚举 \(s[1:i-1]\) 的所有回文后缀，直到满足 \(\operatorname{last}\) 对应的 \(s[1:i-1]\) 的回文后缀的前一个字符为 \(s_i\)，则转移 \(\delta(\operatorname{last}, s_i)\) 转移到的状态即为 \(s[1:i]\) 的最长回文后缀，即 \(s[1:i]\) 的最长回文后缀。

若该转移存在则直接转移即可，否则考虑新建状态 \(x\)，其长度为 \(\operatorname{len}(\operatorname{last}) + 2\)，然后再对 \(\operatorname{last}\) 跳 \(\operatorname{fail}\) 直至找到满足上述条件的另一个回文后缀 \(\operatorname{last}'\)，则 \(\operatorname{fail}(x) = \delta(last', s_i)\)，然后再进行转移。

复杂度证明

详见 OI-wiki。

字符串 \(s\) 的本质不同回文子串的数量至多只有 \(|s|\) 个，则 PAM 的状态数个数是 \(O(n)\) 级别的。证明考虑数学归纳，可证明每增加一个字符本质不同的回文子串数至多增加一个。

在 PAM 中对于某个状态，通过转移可以使状态对应的回文子串的长度 \(+2\)，通过跳 \(\operatorname{fail}\) 可以使状态对应的回文子串的长度至少 \(-1\)，构造 PAM 过程中状态对应的子串长度只会增加 \(n\) 次，则跳 \(\operatorname{fail}\) 的过程至多只会进行 \(2\times n\) 次，则构建 PAM 的时间复杂度也是 \(O(n)\) 级别。

模板题

这题会比 P5496 【模板】回文自动机（PAM） 更好写一点所以把这题放这里了。

P3649 [APIO2014] 回文串
给定一仅由小写字母组成的字符串 \(s\)，定义 \(s\) 的一个子串的存在值为这个子串在 \(s\) 中出现的次数乘以这个子串的长度，求 \(s\) 的所有回文子串的存在值的最大值。
\(1\le |s|\le 3\times 10^5\)。
1S，128MB。

考虑在构建 PAM 过程中对每个状态额外维护 \(\operatorname{cnt}\) 表示该状态对应的回文子串作为 \(s\) 的某前缀 \(s[1:i]\) 的最长回文后缀时的出现次数，构建完 PAM 后考虑对回文树上所有状态求子树 \(\operatorname{cnt}\) 之和即为该回文子串的实际出现次数。

上述过程没有必要通过 dfs 进行，直接倒序枚举所有状态 \(i\)，不断地将 \(\operatorname{cnt}_i\) 累计到 \(\operatorname{cnt}_{\operatorname{fail}_i}\) 中即可。

答案即 \(\max_i (\operatorname{\operatorname{cnt}_i\times \operatorname{len}_i})\)。

代码

//P3649 [APIO2014] 回文串
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
char s[kN];
int n;
//=============================================================
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
namespace PAM {
  const int kNode = kN << 1;
  int nown, nodenum, last, tr[kNode][26], len[kNode], fail[kNode];
  int cnt[kNode];
  char t[kN];
  int Newnode(int len_) {
    ++ nodenum;
    memset(tr[nodenum], 0, sizeof (tr[nodenum]));
    len[nodenum] = len_;
    fail[nodenum] = cnt[nodenum] = 0;
    return nodenum;
  }
  void Init() {
    nodenum = -1;
    last = 0;
    t[nown = 0] = '$';
    Newnode(0), Newnode(-1);
    fail[0] = 1;
  }
  int getfail(int x_) {
    while (t[nown - len[x_] - 1] != t[nown]) x_ = fail[x_];
    return x_;
  }
  void Insert(char ch_) {
    t[++ nown] = ch_;
    int now = getfail(last);
    if (!tr[now][ch_ - 'a']) {
      int x = Newnode(len[now] + 2);
      fail[x] = tr[getfail(fail[now])][ch_ - 'a'];
      tr[now][ch_ - 'a'] = x;
    }
    last = tr[now][ch_ - 'a'];
    ++ cnt[last];
  }
  LL Solve() {
    LL ans = 0;
    for (int i = nodenum; i >= 0; -- i) {
      cnt[fail[i]] += cnt[i];
    }
    for (int i = 1; i <= nodenum; ++ i) {
      ans = std::max(ans, 1ll * cnt[i] * len[i]);
    }
    return ans;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  scanf("%s", s + 1); n = strlen(s + 1);
  PAM::Init();
  for (int i = 1; i <= n; ++ i) PAM::Insert(s[i]);
  printf("%lld\n", PAM::Solve());
  return 0;
}

写在最后

参考：

• https://oi-wiki.org/string/pam/。

学习耗时：3 分钟。

OI-wiki 上直接就“类似后缀自动机”给我笑烂了，幸亏狠狠地学习过 SAM 让发现 PAM 好傻逼。

话说 PAM 居然是 15 年才被发明的，居然有幸学到了本世纪的新知识，令人感慨。

另外本文居然是本博客的第 400 篇可见随笔，四年两个月前为了存点代码的建的小破站到现在居然有 82k 的阅读量了，令人感慨。