C/C++Manacher算法（字符串判断回文串）马拉车算法模板

2018年8月2日 3220点热度 0人点赞 0条评论

简介

朴素的算回文串的办法一般是O（n ^ 2）或 O（n ^ 3）的。而Manacher发明的马拉车算法能将空间复杂度和时间复杂度均优化到O（n）的线性。

具体算法过程是：

1、将字符串中加入#

如 abcde -> ##a#b#c#d#e

举个例子一个字符串s = abbahopxpo，转换为$#a#b#b#a#h#o#p#x#p#o#（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。

定义一个辅助数组p，其中p[i]表示以 i 为中心的最长回文的半径。

这样的话p[i] - 1正好是原字符串中最长回文串的长度

然后只要求出p数据就好了。

评测见洛谷：P3805

模板

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

static const int MAXN = 31000015;

char s[MAXN];
char new_s[MAXN];
int p[MAXN];

int Init();
int Manacher();

int main() {
	scanf("%s",s);
	printf("%d\n",Manacher());
	return 0;
} 
int Manacher() { //马拉车算法主题 
	int len = Init(); //初始化并返回长度
	int max_len = -1;
	int id = 0,mx = 0; 
	for(int i = 1;i < len;++i) {
		if(i < mx) p[i] = min(p[2 * id - i],mx - i); // 2 * id - i指i关于id的对称点j
		else p[i] = 1;
		while(new_s[i - p[i]] == new_s[i + p[i]]) p[i]++;
		if(mx < i + p[i]) {
			id = i;
			mx = i + p[i];
		}
		max_len = max(max_len,p[i] - 1);
	}
	return max_len;
}

int Init() {  //初始化并返回new_s长度 
	int len = strlen(s);
	new_s[0] = '$';
	new_s[1] = '#';
	int j = 2;
	for(int i = 0; i < len;++i) {
		new_s[j++] = s[i];
		new_s[j++] = '#';
	}
	new_s[j] = '\0';
	return j;
}