APTX Blog

A Moe Blog Set 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

模板

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

点赞

发表评论

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