P3805

发表于 更新于 分类于
【模板】manacher 算法

【模板】manacher 算法

按 Jwz 的讲法，Manacher 的实质就是暴力优化。

首先我们压缩一下回文的性质和信息。

定义一个 $d(i)$ 表示以第 $i$ 个位置为中心的一个回文串，它的长度的一半是多少。

比如说 $\texttt{jwzakioi}$ 这个字符串，第 6 个字符是 $\texttt{o}$，则有 $d(6)=2$。因为这个回文串是 $\texttt{ioi}$，$\texttt{o}$ 的左边有 1 个字符，加上它自己就是 2 了。

显然上面这个例子只针对回文串长度为奇数的情况，偶数的情况还需要分开讨论。

但有一种方法可以让我们不分开讨论：

我们尝试修改字符串，在字符的空隙之中加入字符串中不可能出现的字符，比如说 #，于是上述字符串变成了 #j#w#z#a#k#i#o#i#。（因为这里 $\LaTeX$ 不支持在 texttt 里使用 # 所以换了一种方式）

然后按照奇数的方法求就不用再讨论了。

现在我们开始着手考虑 $d(i)$ 怎么求。

我们从前往后处理，现在我们假设处理出来一个 $s’$ 是一个我们已经知道的回文串，并且它所处区间为 $[l,r]$，并且它最靠右边（具体的说就是它的 $r$ 是前面所有我们已知的回文串中最大的一个）。

假如说我们处理到对称中心 $i$。

为了优化暴力，我们考虑提前确定 $d(i)$ 的下界。可以分类来玩：

  1. 假如说 $i\notin[l,r]$，我们也没法怎么确定，那么我们只能确定 $d(i)$ 的下限是 1。

  2. 假如说 $i\in[l,r]$，我们可以假设 $[l,r]$ 的对称中心为 $k$，则 $i$ 关于 $k$ 的一个对称位置 $j=l+r-i$。显然 $d(j)$ 与 $d(i)$ 在区间 $[l,r]$ 内有重合，那这一部分的回文可以直接送给 $d(i)$ 作为其下限。

关于第二种情况，具体可以看 OI wiki 上的解释，如果你能看懂，下面例子可以跳过，看不懂的话我可以举几个具体一点的例子。

对于字符串 $\texttt{tclctatclcx}$，假如说我们处理到最后一个 $\texttt{l}$，设这个位置是 $i$，那么第一个 $\texttt{l}$ 的位置就是我上文所述的 $j$。那么我们有 $d(j)=3$，而其与 $d(i)$ 的重合部分只有在 $[l,r]$ 之内的，即在回文串 $\texttt{clctatclc}$ 之内的部分，即回文串 $\texttt{clc}$，那么我们就确定了 $d(i)$ 的下限是 2。

对于字符串 $\texttt{xclctatclct}$，假如说我们处理到最后一个 $l$，设这个位置是 $\texttt{i}$。那么第一个 $\texttt{l}$ 的位置就是我们所说的 $j$。显然我们已经知道了 $d(j)=2$，按照上述的规则对称过来，$d(i)$ 的下限也是 2。

然而在 $\texttt{xclctatclct}$ 这个例子当中，我们很明显可以看出 $d(i)=3$，也就是这个具体值还需要扩展。怎么扩展呢？暴力扩展就完了！

容易想到 $i\notin[l,r]$ 的情况我们也需要暴力扩展，就不举例子了。

于是我们就有了这一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(ll i=0,l=0,r=-1;i<m;i++) {
  ll k=(i>r)?1:min(d[l+r-i],r-i+1);
  //k 表示目前可以确认的最大的 d[i] 的值 
  //如果说 i 的位置在 (l,r) 之外的话，
  //显然我们最多可以确认 d[i]=1；
  //否则的话，我们可以利用对称性从前面来确定一个较大的值，
  //并与边界的限制取最小值（即取重合部分）。
  while(0<=i-k&&i+k<m&&s[i-k]==s[i+k]) {k++;}
  //暴力在边界外扩展，最终确定 k 的值 
  d[i]=k--;
  if(i+k>r) {l=i-k;r=i+k;}
  //如果这个回文串更靠右，更新 (l,r) 的范围 
}

去掉注释只有 6 行，所以真的挺简单的。

那么直觉上不容易感觉这个复杂度能过。

下面我们给一个根据程序的简短证明。

首先，我们的边界扩展中，假设一次边界扩展的长度是 $\Delta l$，意味着我们需要付出 $\Theta(\Delta l)$ 的复杂度来暴力扩展一个有下界的回文串。然而边界扩展的长度总和 $\sum \Delta l=n$，最后暴力扩展的总复杂度就是 $\Theta(\sum\Delta l)=\Theta(n)$。

加上那些比较 Trivial 的 $O(n)$ 操作，最后的复杂度仍然是 $O(n)$，这个我就不多说了吧？

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll int
using namespace std;

const ll N=2e7;

ll ans;
ll d[N+5];
char a[N+5];

inline void Manacher(char *s_,ll len,ll *ans) {
  static char s[N*2+5];static ll d[N+5];
  memset(s,0,sizeof(s));memset(d,0,sizeof(d));
  s[0]='#';for(ll i=0;i<len;i++) {s[i*2+1]=a[i];s[i*2+2]='#';}
  ll m=len*2+1;
  for(ll i=0,l=0,r=-1;i<m;i++) {
    ll k=(i>r)?1:min(d[l+r-i],r-i+1);
    while(0<=i-k&&i+k<m&&s[i-k]==s[i+k]) {k++;}
    d[i]=k--;if(i+k>r) {l=i-k;r=i+k;}
  }
  for(ll i=1;i<m;i+=2) {ans[i>>1]=max(d[i],d[i+1])-1;}
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {
	
  scanf("%s",a);ll n=strlen(a);

  Manacher(a,n,d);

  for(ll i=0;i<n;i++) {ans=max(ans,d[i]);}
  
  write(ans);
  
  return 0;
}