字符串基础（2.0）

1. Manacher 算法

Manacher 在所有字符串算法中理解起来相对容易，学习它有助于理解 Z 算法。

Manacher 在 NOI 大纲里是 8 级算法。

1.1 相关定义

根据回文串的定义，我们发现奇回文串和偶回文串本质不同。当 $n$ 为奇数时，其 回文中心 为它最中间的位置 n+1/2；当 $n$ 为偶数时，其回文中心为位置 mid 与 $mid+1$ 之间的空隙，其中 mid=n/2​。

此外，定义回文串 $s$ 的 回文半径 为其开头到回文中心形成的字符串长度。当 ∣s∣ 是奇数时，s 的回文半径为 n+1/2​；当 $n$ 是偶数时，$s$ 的回文半径为 n/2​。

容易发现对于 s的某个回文子串 $s[l,r]$，若 $l<r$，则 $s[l+1,r-1]$ 回文。因此，若 $x$ 是 $i$ 的回文半径，则任何小于等于 $x$ 的正整数均为 $i$ 的回文半径。因此，考虑一个回文中心：

• 当它是下标 i 时，存在阈值 $R$ 满足当 0≤j<R 时 $s[i-j,i+j]$ 回文，$R$ 称为以位置 $i$ 为回文中心的 最长回文半径 RiRi​。它可以理解为以 i 为回文中心的回文子串数。
• 同理，当它是 i 与 i+1 之间的空隙时，存在阈值 $R$ 满足当 $0\le j<R$ 时，s[i−j,i+1+j] 回文。

1.2 统一奇偶回文子串

为避免分类讨论，我们尝试将所有偶回文子串转化为奇回文子串。

容易发现，若将所有空隙视作一种独立的 分隔字符，则偶回文子串可视为以对应分隔符为回文中心的奇回文子串。例如 abbbba，若将空隙视为字符 $\text{c}$，则原串变为新串 $\text{cacbcbcbcbcac}$。

考虑原串偶回文子串在新串上的形态。偶回文子串 bb 对应新串 cbcbc，$\text{abbbba}$ 对应新串 cacbcbcbcbcac。手动模拟可知若某分隔符在新串上的最长回文半径为 Ri​（一定是奇数），则它对应的原串最长回文子串长度为 Ri−1。

考虑原串奇回文子串在新串上的形态。奇回文子串 bbb 对应新串 $\text{cbcbcbc}$。手动模拟可知若某原串下标在新串上的最长回文半径为 Ri（一定是偶数），则它对应的原串最长回文半径为 Ri/2​​，最长回文子串长度同样为 Ri​−1。

这样，我们统一了奇回文串和偶回文串从新串转回原串的过程，有效减少了根据最长回文半径 Ri 求解问题的细节，并得到结论：新串的 Ri 表示原串以对应下标或空隙为中心的最长回文子串长度加 1。

1.3 算法介绍

Manacher 算法可以求出以每个位置 $i$ 为回文中心的最长回文半径 Ri​。当然，也可以求出以每个空隙为回文中心的最长回文半径。这种情况已经转化为前者。

首先将 s 的所有字符之间插入相同分隔符，包括头尾，然后在整个字符串头尾插入另外两种不同的分隔符，以防止越界。

朴素想法是对每个回文中心 $i$，从 $1$ 开始从小到大暴力枚举 Ri​。很遗憾，全 $\text{a}$ 串就可以将复杂度卡成 O(n2)。具体复杂度是 $n$ 加上 $s$ 的回文子串数量，出现在不同位置的相等子串 算多个。

只需加上一些优化即可将复杂度变为 $\mathcal{O}(n)$。

回顾朴素暴力，在从 Ri=1 开始枚举的过程中，我们浪费了很多由回文性质带来的有用信息。考虑回文中心 c 及其右端点 r=c+Rc​−1，若当前希望求出 Ri​（$c<i$） 且满足 $i\le r$，则我们完全可以利用 2c−i 处已经求得的 R2c−i 的信息。

具体地，在 $c$ 的最长回文半径范围内，因为 $c<i\le r$，所以 $2c-i$ 和 i 在该范围内对称。也就是说，在 [c−Rc+1,c+Rc−1]范围内，以 $2c-i$ 为对称中心的回文串也是以 i 为对称中心的回文串。因此，我们得出 Ri≥min⁡(r−i+1,R2c−i)。

如上图，因为黄色部分回文，所以对于以 $2c-i$ 为回文中心且落在黄色部分的回文串（橙色部分），一定也在 i 处出现。

因此，考虑维护已经计算过的所有回文中心对应的最长回文子串的右端点的最大值 r=max⁡p=1i−1p+Rp−1 以及对应回文中心 c。

对于当前位置 $i$，若 $r<i$，则从 $0$ 开始枚举求得 Ri​。此时每次扩展均使得$r$ 向右移动 $1$。

否则 i≤r，利用回文性质和已经求出的信息，先将 Ri 赋值为 min⁡(r−i+1,R2c−i)，再逐位扩展：

• 若 R2c−i<r−i+1，则 RiRi​ 就等于 R2c−i​。否则根据对称性 R2c−i​ 可以更大，与其最大性矛盾。
• 否则 RiRi​ 被初始化为 r−i+1，使得每次扩展都会将 $r$ 向右移动 $1$。

综上，时间复杂度线性。

模板题 P3805 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2.2e7 + 5;
int n, m, ans, R[N];
char s[N], t[N];
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  t[0] = '!', t[m = 1] = '@';
  for(int i = 1; i <= n; i++) t[++m] = s[i], t[++m] = '@'; // 间隔插入字符.
  t[++m] = '#';
  for(int i = 1, c = 0, r = 0; i < m; i++) { // r 是最右回文边界, c 是对应回文中心.
    R[i] = r < i ? 1 : min(R[c * 2 - i], r - i + 1); // 若 i <= r, 则根据对称性继承信息.
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    ans = max(ans, R[i] - 1);
    if(i + R[i] - 1 > r) c = i, r = i + R[i] - 1; // 更新 r 和 c.
  }
  cout << ans << endl;
  return 0;
}

1.4 结论与应用

Manacher 本身证明了一个关于回文子串的结论：一个字符串的本质不同回文子串个数不大于 n。因为所有以 $i$ 为回文中心的长度小于等于 min(r−i+1,R2c−i​) 的回文子串均与以 2c−i 为回文中心的对应长度的回文子串相等。故以 $i$ 为回文中心，每找到一个在此之前没有出现过的回文子串，均会使 r 增加 2（找到回文子串后，因为分隔符回文再扩展一步）。注意，使 $r$ 增加并不一定代表找到新的回文子串。

当然，我们也可以不借助 Manacher 直接证明这一结论。考虑在每个回文子串第一次出现处计入贡献。若存在两个本质不同回文子串 $p,q$ 在同一右端点处贡献答案，不妨设 ∣p∣<∣q∣，则根据回文性 q[1,∣p∣]=p，与 $p$ 第一次出现在 $q[|q|-|p|+1,|q|]$ 处矛盾。因此一个右端点至多贡献一个本质不同回文子串。

利用 Manacher，我们可以求出以每个字符开头或结尾的最长回文子串：考虑位置 $i$ 及其最长回文半径 Ri​，若 i+Ri​−1>r，根据算法，用 $i$ 更新 $r$。更新前枚举j∈[r+1,i+Ri​−1]，若 tjtj​ 对应原串字符 sk​ 而非分隔符，则原串中以 sk 结尾的最长回文子串长度为 $j-i+1$。通过分奇偶性讨论和模拟可证其正确性。代码实现见例题 P4555。

1.5 例题

UVA11475 Extend to Palindrome

找到最小的使得 s[l,r] 为回文串的 $l$，则答案即 $s$ 加上 $s[1,l-1]$ 翻转后的结果。代码。

P3501 [POI2010] ANT-Antisymmetry

借鉴 Manacher 的思路，我们对每个位置求出最长 Anti-symmetry 半径。同样的，记录最右边的回文区间，快速继承和扩展做到均摊线性。代码。

P4555 [国家集训队] 最长双回文串

对每个位置求出以该字符结尾和开头的最长回文子串 lfti​ 和 rti

时间复杂度线性。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ans, R[N], lft[N], rt[N];
char s[N], t[N];
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  t[0] = '!', t[m = 1] = '@';
  for(int i = 1; i <= n; i++) t[++m] = s[i], t[++m] = '@';
  t[++m] = '#';
  for(int i = 1, c = 0, r = 0; i < m; i++) {
    R[i] = i > r ? 1 : min(R[2 * c - i], r - i + 1);
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    if(i + R[i] - 1 > r) {
      for(int j = r + 1; j < i + R[i]; j++) if(j & 1 ^ 1) lft[j >> 1] = j - i + 1; // 新串的偶数位置对应一个原串字符.
      c = i, r = i + R[i] - 1;
    }
  }
  for(int i = m - 1, c = m, r = m; i; i--) { // 倒过来做一遍 Manacher.
    R[i] = i < r ? 1 : min(R[2 * c - i], i - r + 1);
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    if(i - R[i] + 1 < r) {
      for(int j = i - R[i] + 1; j < r; j++) if(j & 1 ^ 1) rt[j >> 1] = i - j + 1;
      c = i, r = i - R[i] + 1;
    }
  }
  for(int i = 1; i < n; i++) ans = max(ans, lft[i] + rt[i + 1]);
  cout << ans << endl;
  return 0;
}

P1659 [国家集训队] 拉拉队排练

因为题目要求奇回文串，所以只考虑以下标 i 为回文中心。若新串位置 $k$ 对应原串下标 $i$，则此时所有长度 j∈[1,Rk2] 的回文半径均存在，相当于对 1,3,⋯,Rk​−1 进行单点加，最后全局查询。差分维护即可。

时间复杂度是快速幂的 O(nlog⁡n)。代码。

P5446 [THUPC2018] 绿绿和串串

如果 prei 能生成 $s$，则以 $i$ 为回文中心时，要么存在顶到结尾的回文串，要么存在顶到开头的回文串且 pre2i−1​ 能生成 $s$。

Manacher 求出每个位置的最长回文半径后倒过来 dp 一遍即可。

时间复杂度 O(n)。代码

（ps：本文是用Markdown，所以转过来有些格式不太对，抱歉）