时间戳

首页 > 技术文章 > manacher算法笔记

manacher算法笔记

MYCui 2020-10-26 11:52 原文

吐槽

暑假上的字符串课没听懂几个字，所以现在像在学新算法一样

好像就是在学新算法，不管了

其实讲真的字符串的算法都比较巧妙啊!KMP,AC自动机,Manacher,SAM,这些算法都是思想非常巧妙的,而且代码比较短！所以 很难，学不会 要好好理解

这是本蒟蒻字符串专题学习的第一个算法,为什么不是KMP?因为题单第一道题目就是用的Manacher(bushi .

(图暂时没放，有时间画了就放上来)

字符回文串算法

好了扯谈结束.

ＯＩ中一直有一个经典的问题，求回文子串。

然后大概有三种算法来解决这个问题：

  • 中心扩展法
  • 动态规划法
  • Manacher算法

这里讲的就是Manacher算法.

为什么上面两个它们不行？

第一个不能处理偶回文(找不到中心!)而且时间复杂度O(\(n^2\))，

第二个时间复杂度O(\(n^2\))，显然也不大行的样子

但是我们的Manacher算法，它的时间复杂度为O(n),并且可以适应奇回文和偶回文！这个算法大大滴好！

所以我们用Manacher 来解决问题.

Manacher 算法

算法思想：

将偶回文串转化为奇回文串，同时利用已经处理过的信息，借助对称(回文串具有对称的性质)来对当前处理的点进行扩展。

规定算法概念:

定义\(R\)是当前扩展到的所有回文串的最右边界

定义\(pos\) 是右边界为\(R\)且第一次扩展到\(R\)的时候对应的中心点

定义\(L\)是\(R\)关于\(pos\)的对称点(也就是以\(pos\)为对称中心的回文串的左端点),\(L = 2* pos - R\)

定义\(x\)的回文半径是我们求到的以\(x\)为中心的最长回文串的左边界到\(x\)的长度,规定为\(p[x]\)

定义\(i\)是当前处理到的，要求以\(i\)为中心的回文半径

算法流程:

第一步，先把偶回文转化为奇回文,这个的处理就是在原串的基础上，每两个字符中间加上一个奇奇怪怪的字符

例如原串为: str = "a , b , b , a , b , a "
转化后就为:str' = "^ , a , # , b , # , b , # , a , # , b , # , a , $ "

放张图片:

BnH0Ug.png

你数一数是不是偶回文就变成了奇回文了呀?

细心的小伙伴已经注意到了,第一个加入的字符和最后一个加入的字符不一样　！这个是为了处理边界，后面会用到

第二步,对于新串中的每一个点求它们的回文半径.

按照前面的规定，我们现在知道了\(R\)以及\(pos\)，还有当前我们要求回文半径的点为\(i\)，同时显然\(i > pos\)，而且我们已经知道了扩展后的字符串的\(i\)前面字符的所有\(p[j]\),\((0 <= j < i)\)

我们规定\(i\)关于\(pos\)对称的点为\(i'\) , \(i' = 2 * pos - i\)

然后分情况讨论:

以下内容为算法核心!!

  • \(i\) < \(R\):

那么\(i'\)就会大于\(L\)小于\(pos\)

\(1.\)如果\(p[i'] + i <= R\)，这就告诉我们，以\(i'\)为中心的回文串被包含在回文串\([L,R]\)(也就是当前右端点最右的回文串).

那么因为\([L,R]\)是一个回文串，这个串\([L,R]\) 就具有对称性，那么\(p[i] = p[i']\)

\(2.\) 如果\(p[i'] + i > R\),这就告诉我们，以\(i'\)为中心的回文串 一定不是 完全包含在回文串\([L,R]\)中。

但是至少我们可以知道，以\(i'\)为中心的回文串包含在回文串\([L,R]\)中间的部分，根据对称性,以\(i\)为中心的回文串的长度一定大于等于这部分,然后我们再进行暴力扩展.

综合上面两种情况，我们可以得到一条核心伪代码:

p[i] = min(p[i'],R - i + 1);//前面是代表的被完全包含的情况，后面则是没有被完全包含的情况，两种情况因为是求可行情况，所以是求min

\(i'\)实际代码是写成\(2 * pos - i\)

  • \(i\) >= \(R\)

这没办法，前面的信息已经用不上了，暴力修改，同时更新\(R\)以及 \(pos\),此时初始化\(p[i]等于1\)

核心伪代码:

      while(str[i + p[i]] == str[i - p[i]])p[i] ++;
       // 这里就是暴力扩展，然后前面的伏笔边界处理就在此用上了，因为边界字符不同，所以我们不会把边界算进去

算法核心到此结束

然后就算法至此完结撒花了,给出算法核心代码:

int manacher()
{
	int R = 0 , pos = 0 ,maxlen = 0;
	for(int i = 1 ; i <= lenstr ; i ++)
	{
		if(i <= R)
			p[i] = min(p[2 * pos - i],R - i + 1);
		else p[i] = 1;
		while(str[i - p[i]] == str[i + p[i]])p[i] ++;//暴力枚举
		if(i + p[i] - 1 > R)
		{
			R = i + p[i] - 1;
			pos = i;//更新Ｒ以及pos
		}
		maxlen = max(maxlen,p[i] - 1);//更新maxlen
	}
	return maxlen;
}

严谨时间复杂度证明: https://segmentfault.com/a/1190000008484167 翻到最下面

Code

最后还是贴一下模板完整代码(luogu上的，居然是蓝题......)

(主要是填补特殊符号那一段代码):

#include <bits/stdc++.h>
using namespace std;
char a[31000005];
char str[31000005];
int p[31000005];
int lena,lenstr;
void manacher()
{
	int R = 0 , pos = 0 ,maxlen = 0;
	for(int i = 1 ; i <= lenstr ; i ++)//第一个以及最后一个只是为了处理边界，我们枚举的时候没必要枚举那两个，没什么用
	{
		if(i <= R)
			p[i] = min(p[2 * pos - i],R - i + 1);
		else p[i] = 1;
		while(str[i - p[i]] == str[i + p[i]])p[i] ++;//暴力枚举
		if(i + p[i] - 1 > R)
		{
			R = i + p[i] - 1;
			pos = i;//更新Ｒ以及pos
		}
		maxlen = max(maxlen,p[i] - 1);//更新maxlen
	}
	cout << maxlen;
}
int main()
{
	cin >> a;
	lena = strlen(a);
	str[0] = '^';//这个字符随便定
	for(int i = 1 ; i <= 2*lena + 1; i ++)
	{
		if(i % 2 == 1)str[i] = '#';
		else str[i] = a[i / 2 - 1];
	}
	lenstr = 2 * lena + 1;
	str[lenstr + 1] = '$';
	//实际上我们用到的是1 到 lena*2+1　这段区间的字符，最前面和最后面的两个是为了处理边界
	manacher();
	return 0;
}

推荐阅读