题解：P3805 【模板】manacher

算法简介

Manacher 在

1975

年发明了一个算法，可以在

O(n)

的时间复杂度内寻找一个字符串的所有回文串，因此这种算法以他的名字冠名（中文谐音马拉车）。

算法思想

主要是靠回文串的“对称”性质，优化大量不必要的计算，先来看个例子：

对于一个字符串，如果我们要找到它的全部长度为奇数的回文字串，可能会用这样的朴素算法：

遍历字符串
对于当前位置 $i$ ，以其为对称轴向两侧“扩展”，像这样：

CPP

int cnt=1;
while(i-cnt&&s[i+cnt]==s[i-cnt])++cnt;

这样可以确定：以

i

为中心的最长的回文字串的“半径”为 cnt。我们称这个值为 回文半径，用一个 p 数组存下来。
但不难看出来，面对极端情况（字符串只含一种字符），复杂度为

O(n^2)

。

怎么优化呢？
首先我们可以注意到：因为我们是按顺序遍历的，也就是说，一个位置的答案确定好之后就不会发生改变了。
考虑到这点，可能我们在优化时要尽可能利用过去得到的答案。

那么如果我们正在考虑

i

，在什么情况下，计算

p_i

要用到

p_j

的值呢？
这时我们就能注意到了：如果

i

和

j

是一个回文串

s^*

中对称的位置，那么，以

j

为中心的最长回文字串中属于 $s^*$ 的部分一定也属于以

i

为中心的最长回文字串中，事实上，这正是 Manacher 的核心思路。

关于实现方式，有一个巧妙的方法：因为这个优化只有在

i

被一个回文字串包括时才有意义，所以我们只有维护“右端点最靠右的回文串”的必要，如此一来，我们就可以设计出下面的算法流程：

设 $C$ 为 $s^*$ 的中心位置， $R$ 为 $s^*$ 的回文半径。初始化两个为 $0$ 。
遍历字符串
找到 $i$ 在 $s^*$ 中的对称位置 $2\times C-i$ ，我们称之为 $i_m$ 。
倘若 $i_m$ 有意义（即大于 $0$ ），将 $p_i$ 赋成 $\min\{p_{i_m},R-i\}$ 。
直接从 $p_i$ 开始扩展。
如果扩展完得到的 $i+p_i$ 大于 $R$ ，用 $i$ 和 $p_i$ 替换 $C$ 和 $R$ 。

这个时候可能会有点怪，因为还是扩展了，但让我们仔细思考一下什么时候才会扩展。
很显然，如果扩展完没有更新

C+R

，事实上，根本就不会发生扩展。
反证法：
如果能扩展，且最终没有更新

R

，则至少以

i

为中心的最长回文字串会包含

i-p_{i_m}-1

和

i+p_{i_m}+1

。
而这两个字符分别与

i_m+1

和

i_m-1

相等，如果前二者是相等的，则后二者也相等，但以

i_m

为中心的最长回文字串没有包含后二者，出现矛盾，假设不成立。

这样一来，每次扩展一定会把

C+R

往前推，但这个值很显然不会超过

n

，所以扩展的次数也不会超过

n

次，再算上遍历，总的复杂度还是

O(n)

。

如果你按照这个思路去写代码并提交，肯定无法 AC，因为我最开始的例子就只考虑的长度为奇数的回文子串，不过，要考虑长度为偶数的情况，有一个巧妙的方式：
在每个字符之间插入一个 罕见的 字符，比如 “#”，也就是代表两两字符之间的空位，再加入一头一尾两个不同的哨兵字符，就能处理全部的情况了（而且这样得到的最大回文半径直接就是真实的回文长度）。

Talk is cheap,show me the code

CPP

#include<bits/stdc++.h>
using namespace std;

const int N=3e7+5;
string s,t;
int l;
int p[N],C,R,ans;

void dl(){    //调整字符串
	t="^#";
	for(int i=0;i<l;i++)t+=s[i],t+='#';
	t+='$';
	l=t.size();
}

void solve(){  //获得 p 数组
	for(int i=1;i<l-1;i++){
		int mirri=2*C-i;
		if(i<R)p[i]=max(0,min(R-i,p[mirri]));
		int cnt=0;
		while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++,cnt++;
		if(i+p[i]>R)C=i,R=p[i]+i;
		ans=max(ans,p[i]);
	}
}

int main(){
	cin>>s;
	l=s.size();
	dl();
	solve();
	cout<<ans;
	return 0;
}

题解：P3805 【模板】manacher

文章操作

算法简介

算法思想

Talk is cheap,show me the code

相关推荐

评论

题解：P3805 【模板】manacher