今天是星期六。

那就打一下 Atcoder 吧，我想。

诶，还有 56 分钟，不妨去洛谷水一水题。

哎我去怎么我连 Manacher 都不会了。

那我还是来写一篇文章讲一讲吧。

例子

洛谷P3805

题意：给定一个小写字母串 $s$，求 $s$ 中最长的回文串。需要线性做法。

以下讲解均为 1-indexed。

首先如果回文长度是奇数就很爽，因为这样回文中心可以用一个整数表示。但要是偶数就会出现卡在两个字母中间的问题。

为了解决这点，我们有一个天才般的解决方法：在每两个字符之间插一个特殊字符。

为什么这能解决我们的问题？

如果我们不插入字符，那么长度为偶数的串回文中心就会是当前的空气。那我们让空气具象化，也就是插入一个字符就可以完美解决。同时对于长度为奇数的串，在左右两边同时扩展的时候多扩展一个特殊字符根本不会带来任何问题。

现在长度被我们乘了 $2$。为了避免除法，我们把要求的长度变成半径。例如，ababa 的长度是 $5$，半径是 $3$。

反正我们要求所有串中的最大，肯定要枚举每一个字符作为回文中心。那就对每一个都记录一下吧。设 $p_i$ 表示以 $i$ 为中心的所有回文串中的最大回文半径。

显然的，$p_i$ 首先有如下求法：

1

while(s[i-p[i]]==s[i+p[i]])p[i]++;

我们将这个称为计算 $p_i$ 的“朴素方法”。

在计算到这个位置之前，我们说不定已经计算了什么，重复计算是要极力避免的。可是，我们计算了什么呢？

我们记录已有的所有回文串中，右边界最靠右的那个串的中心 $mid$ 与右端点 $rgt$。初始时，$mid$ 与 $rgt$ 均为无意义负值。

现在我们考虑到了位置 $i$。

我也不知道怎么办，分类讨论一下吧。

$i>rgt$

混沌未开。我们什么也不知道。

那，就直接用朴素方法计算吧。

$i<rgt$

记 $i \prime$ 为 $i$ 关于 $mid$ 的对称点。由中点公式可以轻易的得出 $i \prime = (2 \times mid - i)$。

我们算过了什么。算过了什么？

没错，算过了 $p_{i \prime}$。我们知道，$s_{i \prime \sim mid}$ 与 $s_{mid \sim i}$ 一定是对称的。所以，$p_i$ 就等于 $p_{i \prime}$ ！

……

吗？

考虑这样一个情况：

这时 $p_{i \prime}$ 太大了，以至于在 $rgt$ 后面的东西，我们，一无所知。可以确定的是，以 $i$ 为中心的回文串的右端点至少是 $rgt$，也即回文半径为 $rgt-i$。那没办法了，就用朴素方法计算吧。

在计算后，尝试更新 $mid$ 和 $rgt$。

现在，一切 $p_i$ 均已得知，答案即为：

可是……怎么就是线性的了？这可是调用了很多次朴素计算啊。

我们不妨考察 $rgt$ 的变化。

对于情况 $i>r$，显然朴素算法每循环一次就会将 $rgt$ 往后推进 $1$。

而对于情况 $i<r$，当 $p_{i \prime}$ 较小的时候不会调用朴素算法，而较大的时候朴素算法一定会将 $rgt$ 向后推进。

因此得出，朴素算法的每一次循环都会将 $rgt$ 向后推进 $1$。又因为 $rgt$ 的上限是 $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

#include<bits/stdc++.h>
using namespace std;
int p[40000005];
int main(){
	string s="##";
	char c=getchar();
	while(c>='a'&&c<='z'){
		s+=c;
		s+='#';
		c=getchar();
	}
	int n=s.size();
	s=' '+s;//转为 1-indexed
	int mid=0,rgt=-1,ans=0;
	for(int i=1;i<=n;i++){
		if(i>rgt)p[i]=1;//情况 i>rgt
		else p[i]=min(p[2*mid-i],rgt-i);//情况 i<rgt
		while(s[i+p[i]]==s[i-p[i]])p[i]++;//暴力扩展
		if(p[i]+i>rgt){//更新 rgt 与 mid
			rgt=p[i]+i;
			mid=i;
		}
		ans=max(ans,p[i]);
	}
	cout<<ans-1;
	return 0;
}

简洁。优美。但是 7 级难度很明显是恶评。

后记：由于在打 Atcoder 时仍在想这篇文章的事，我 A 题看错题了。乐。