Manacher算法详解及模板(求解最长回文串)

Manacher用于求解最长回文子串。所谓回文串，便是"abccba"或是斗鸡山上山鸡斗这一类的，你会发现从左到右和从右到左读都是同样的内容。而最长回文子串便是求出给定串中最长的那一个回文串。在没了解Manacher之前，我们可以直接暴力枚举，时间复杂度$O(n^3)$，也可以用聪明一点的方法，每次枚举一个点，比较它左右距离相同的点是否相同，时间复杂度$O(n^2)$。不过 Manacher时间复杂度为$O(n)$ 用过中心检测法（就是上面说的$O(n^2)$的算法）的都知道对于奇数回文串和偶数回文串的处理是不同的，奇数回文串有$2n+1$个字符，所以中心字符一定只有一个。而同理，对于偶数回文串，中心字符有2个。这样1个和2个的情况不好处理，所以我们将给出的串统一转化为奇数回文串。我们将每一个字符的左边和右边都添加一个字符（这个字符是输入中所没有的）。一般都为#。比如说abc和abcd这两个串转化后就为#a#b#c#和#a#b#c#d#。长度分别为$7$和$9$这样无论奇偶都能被转换成奇数回文串了. 其实在我看来,Manacher就是优化后的中心检测法,和KMP算法类似,Manacher的思想也是避免”匹配”失败后的下标回退

转载注明出自bestsort.cn,谢谢合作

下面正式开始分析算法 首先,我们需要了解一个叫做回文半径的东西如上图,P点为中心点,ABCDEDCBA构成一个回文串,那么$r$的长度就是该回文串的回文半径我们都知道,中心检测法是依次枚举每一个点的回文半径,取所有回文半径的最大值.当当前字符满足回文条件的时候,检测下一个字符,否则返回当前半径长度,然后回文半径长度回退为1开始检测下一点.但是这个回退是可以避免的 这里用图解的形式解释一下: 先设之前已经匹配好了的最大回文半径长为$R$,然后设当前点的回文半径为$r$,其中,$r$的起点一定大于$R$的起点(因为处理$r$的时候$R$已经处理好了) 那么$R$和$r$的关系一定有如下3种情况 1.r右端点<=R右端点&&r左端点>=R中心点,如图示这种情况我们这里先给出$r$段关于$R$中心点所对称的线段$r_1$ 因为$r$和$r_1$是关于$R$中心点对称的，所以$r$的回文半径一定等于$r_1$ 对于此种情况,可以从图中看出来$r$的回文半径一定小于$R$的回文半径,因为图中以蓝色竖线为起点包含的字符数小于以黑色竖线为起点所包含的字符数.所以这种情况下,回文半径最大值仍为$R$. 2.右端点< R右端点&&r左端点< R中心点，如下图还是和1一样，我们先画出关于R中心点对称的$r_1$ 我们在这副图中也能找到对称的线段,如下图红色和红色对对称，蓝色和蓝色对称，所以，$r$和$r_1$仍然关于$R$中心点对称，也就是$r$的回文半径依旧等于$r_1$的回文半径. 3.r右端点>R右端点** 还是和上面一样处理成下图靠下的$蓝色虚线+蓝色实线+黄色实线=之前的r$ 有了上面的基础，我们现在唯一需要查询的就是黄线部分了，这里将回文半径由$R$继续扩大就好

到此,原理说完了,我们来看看代码怎么写的吧

先放上伪码

/*
String:加'#'处理后的回文串
MaxR:最长回文半径
flag:最长回文半径对应的中心点下标
cnt[i]:以i为中心对应的回文半径
length:String长度
*/  
for i to length
    if MaxR > i:               //如果当前点被最长回文半径包含
        cnt[i]=min(cnt[2*flag-i],MaxR-i) //取情况1和情况2中较小的（防止超出MaxR范围）
    else:
        cnt[i]=1
    while(String[i+cnt[i]] == String[i-cnt[i]]):
        cnt[i]++;
    if i+cnt[i] > MaxR:
        MaxR=i+cnt[i],flag=i;

下面上正式代码

int cnt[maxn];
void Manacher(char s[],int len) {//原字符串和串长
    int l = 0;
    String[l++] = '$'; // 0下标存储为其他字符,防止越界
    String[l++] = '#';
    for (int i = 0; i < len; i++) {
        String[l++] = s[i];
        String[l++] = '#';
    }
    String[l] = 0; // 空字符
    int MaxR = 0;
    int flag = 0;
    for (int i = 0; i < l; i++) {
        cnt[i] = MaxR > i ? min(cnt[2 * flag - i], MaxR - i) : 1;//2*flag-i是i点关于flag的对称点
        while (String[i + cnt[i]] == String[i - cnt[i]])
            cnt[i]++;
        if (i + cnt[i] > MaxR) {
            MaxR = i + cnt[i];
            flag = i;
        }
    }
}
/*
* String: $ # a # b # a # a # b # a # 0
* cnt:    1 1 2 1 4 1 2 7 2 1 4 1 2 1 
* cnt 即每个点的回文半径
*/