APTX Blog

A Moe Blog Set Up By APTX

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

文章目录[隐藏]

简介

朴素的算回文串的办法一般是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;
}

参考地址:https://segmentfault.com/a/1190000008484167

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注