【知识点】Manacher算法详解

Manacher算法

算法简介

(Manacher) 算法，即“马拉车”算法，是一种高效（(O(n))）的求最长回文子串的算法。相比于 (KMP) ，(Manacher) 也许更好理解一些。

算法原理

对于传统的暴力解法，求最长回文子串的方式应该是对于每个位置 (i) ，向两边“扩大”以寻找回文子串，再记录答案。易证，此解法时间复杂度为 (O(n^2))。

众所周知，每一个毒瘤算法都有一个暴力的开头。

(Manacher) 算法首先要对原字符串进行处理。因为回文串分为两种，“奇回文”和“偶回文”：

1. "abcba"
2. "abba"

首先，在每两个字符之间放入一个没有出现在原串的字符，如 (mathtt{'#'}) ；接着，将字符串的两边插入另外两个不同的，且没有出现在原串的字符，如 (mathtt{'@'}) 和 (mathtt{'$'}) 。操作结果如下：

1. "@a#b#b#a$"
2. "@a#b#c#b#a$"

神奇的事情发生了，“奇回文”和“偶回文”都转化成了“奇回文”。同时，在判定回文串的过程中也不用判边界了，因为修改后字符串边界字符不一样。

除此之外， (Manacher) 算法还引入了一个数组 (p) ， (p_i) 表示以位置 (i) 为中心的“最长回文半径”。对于字符串 (mathtt{"@#a#b#b#a#d#c#a#c#d#a#$"}) 如表所示:

(i)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
(s_i)	@	#	a	#	b	#	b	#	a	#	d	#	c	#	a	#	c	#	d	#	a	#	$
(p_i)	1	1	2	1	2	3	2	1	2	1	2	1	2	1	6	1	2	1	2	1	2	1	1

显然，最终答案就是 (max{p_i-1}) 。那么 (Manacher) 算法就讲完了……等等， (p) 数组怎么求？

算法过程

推荐阅读~

首先，看下图：

引入两个变量， (mx) 和 (id) ， (mx) 表示以 (id) 为中心点的最大回文子串右边界。

假设现在要求 (p_i) ，那么就有：

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

这样就可以加快速度。但是……为什么？为什么为什么？？？

设 (i'=id*2-i) ，也就是说，(i') 是 (i) 关于 (id) 的对称点。因为是从前往后循环， (p_{i'})是已知的。下面开始分类讨论：

• 若 (p_{i'}>mx-i) ，可得以 (i') 为中心，以 (mx) 的对称点 (mx') 到 (i') 的距离为半径形成的回文字符串是存在的，并且 (id) 到 (mx') 与 (id) 到 (mx) 一一对应，所以 (mx) 是 (i) 目前可以更新到的最大回文半径；
• 若 (p_{i'}<mx-i) ，也就是 (i') 的回文半径小于 (mx') 到 (i') 的距离，可得 (p_i=p_{i'}) 。

于是就有了你看到的反人类代码。

完整代码

int manacher(string &s_src)
{
    /*
     * @params s_src为源字符串，s为预处理后的字符串
     */
      string s="@";
    for(auto &ch: s_src)
    {
        s.push_back('#');
        s.push_back(ch);
    }
    s+="#$";
    int id,mx=0,res=0;
    for(int i=1;i<s.size()-1;i++)
    {
        if(i<=mx)
            p[i]=min(p[id*2-i],mx-i);
        while(s[i-p[i]]==s[i+p[i]])
            p[i]++;
        if(i+p[i]>mx)
            id=i,mx=i+p[i]-1;
        res=max(res,p[i]-1);
    }
    return res;
}