APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年8月2日 2163点热度 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;
}

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

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ Manacher 回文 回文串 字符串 模板 洛谷 算法 落谷
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
#动漫#《学园孤岛》OP/ED/角色歌下载 #同人志#C90:《这个美术社大有问题》同人志推荐 Nginx:301永久重定向配置以及自动跳转https配置 寿屋:まちカドまぞく 千代田桃 几种云端 VSCode/类 VSCode 方案对比与部署 C++快速幂
标签聚合
C/C++ HTML 动漫 C++ ST OI 洛谷 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang