「笔记」回文自动机-526互联

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

写在前面

其实这东西学名叫 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;
}