Part 0. 引子

自己接触 OI 已经很长时间了，但是字符串仍然处于门外汉的尴尬境地。

于是，我决定狂补字符串。

Manacher（中文谐音马拉车），是解决最长回文串的一种高效算法。他能够在 Θ(n)\Theta(n) 的时间内解决这个问题，同时代码很简洁。

Part 1. 先聊聊暴力

暴力方式就是所谓的“中心扩展法”。说白了就是枚举每一个字符，然后往左右两边分别扩展，确定以这个字符为中心的回文有多长。

很明显，这个算法的时间复杂度是 O(n2)O(n^2) 的。当然了，如果这个字符串长这个样子：

1
qwertyuiopasdfghjklzxcvbnm

代码在进行计算的时候，啥也扩展不出去，每一次刚往外扩展了一格，就发现无法匹配。结果就是整个代码的运行几乎是 O(n)O(n) 的。

但是如果这个字符串长这个熊样呢？

1
aaaaaaaaaaaaaaaaaaaaaaaaaaa

这个字符串和上面那个完全一样长，但是我们每一次都要扩展到两端才能停止。这就是个极为低效的 O(n2)O(n^2) 了。

出题人肯定会用第二种数据，想办法卡掉暴力中心扩展法的。

Part 1121\frac{1}{2}. 在此之前

对于字符串，我们进行一个小小的预处理：本来的字符串中，既有长度为奇数的回文，也有长度为偶数的回文。长度为偶数的回文判断起来要麻烦一些，因为他没有一个确切的中心，所以我们不得不两个两个地枚举偶数回文的中心。

有没有方法简化呢？很简单，我们把回文变成这样就行了。

1
2
3
4
原来：
addfggfe
现在：
$#a#d#d#f#g#g#f#e#%

具体插入了什么字符不重要，重要的是这样一来我们本来的偶回文就变成了奇回文，中心是一个插入的字符。

因此我们接下来只讨论奇回文的情况。

Part 2. 分析暴力

在暴力的时候，我们会发现重复的一个字符被扫描了许多便。比如说，在我们对于aaaaaaaaaaaaaaaaaaaaaaaaaaa 进行操作的时候，最头上的那个a被扫描了13遍。

但是我们每一次的中心是不一样的啊！不能简单地记忆化，因为我怎么知道下一次是谁扫到我了？

不过，仍然有解决方法。

Part 3. 回文的镜像也是回文

虽然我们不能直接记忆化，但是我们来考虑一个特殊情况：

当前我们要求 ii 位置的回文串长度，此时我们有一点 RR，是整个字符串中已经扫描过（注意，由于中心扩展法是按照中心从左往右遍历的，所以最靠右的可能并不是最右边的中心） 的最靠右的字符，CC 是扫描到他的中心。此时，令 jj 为 ii 关于 CC 对称的位置，以他为中心的回文长度是已经知道的，那么我们就可以同理得到，ii 的回文也是这么长。

那还算啥啊。

不过这是特例。还有其他情况。

考虑这种情况。jj 我们确实知道了，但是他超出了 CC 回文的范围。此时我们不能继续利用刚才的方式，正确的做法是这样：我们可以确定，图中所示的 ii 所在的标红区域是回文。后面的我们直接暴力扩展即可。扩展完成后更新 RR 和 CC。

设以 xx 为中心的最长回文半径为 P[x]P[x]，在实际操作时，两种情况分别如下：

  • 情况一：Pi=PC−(i−C)=P2C−iP_i=P_{C-(i-C)}=P_{2C-i}
  • 情况二：Pi=R−iP_i=R-i，暴力扩展

其实我们可以把上面两种情况取个 min⁡\min，然后直接暴力扩展，第一种情况下可以证明整个过程不会再次扩展任何值。

当然了，还有第三种情况，就是 R<iR<i，这就没救了，只能暴力扩展。

Part 4. 复杂度分析

上面这个东西好像复杂度也是 O(n2)O(n^2) 的啊？

不，我们会发现，只要有 i<Ri < R，我们都不会再进行计算，直接调用现成的值，当 i≥Ri \ge R 的时候，我们确实会扩展，但是扩展以后我们的 RR 也随之更新了啊！因此这个算法的复杂度是 O(n)O(n)。

Part 5. Code for P3805

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
#include<iostream>
#define endl '\n'
using namespace std;
const int N=5e7+10;
int p[N];
int manacher(string s){
    int c=1,r=0;
    int n=s.size();
    for(int i=1;i<n;i++){
        p[i]=1;
        if(i<r)p[i]=min(p[2*c-i],p[c]-i+c);
        while(s[i-p[i]]==s[i+p[i]]&&i>=p[i])p[i]++;
        if(p[i]+i>r){
            r=p[i]+i;
            c=i;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
		if(p[i]>ans)ans=p[i];
	}
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    string t="*#";
    for(int i=0;i<s.size();i++){
        char tt[3]={s[i],'#'};
        t.append(tt);
    }
    t.append("#&");
    cout<<manacher(t)-1<<endl;
    return 0;
}