一文读懂回文子串 Manacher 算法

正文

请到「今天看啥」查看全文

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

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

可以看出，p[i] - 1正好是原字符串中最长回文串的长度。

接下来的重点就是求解 p 数组，如下图：

设置两个变量，mx 和 id 。mx 代表以 id 为中心的最长回文的右边界，也就是mx = id + p[id]。

假设我们现在求p[i]，也就是以 i 为中心的最长回文半径，如果i < mx，如上图，那么：

if (i < mx)

p[i] = min(p[2 * id - i], mx - i);

2 * id - i为 i 关于 id 的对称点，即上图的 j 点，而p[j]表示以 j 为中心的最长回文半径，因此我们可以利用p[j]来加快查找。

代码

/**

*

* author : 刘毅（Limer）

* date   : 2017-02-25

* mode   : C++

*/

#include

#include

#include

using namespace std;

char s[1000];

char s_new[2000];

int p[2000];

int Init()

请到「今天看啥」查看全文