Manacher(马拉车)算法

· · 个人记录

第一篇博客，记录算法学习

  马拉车算法是一种可以用线性复杂度解决求最长回文子串的算法，下面将具体介绍该算法的思想与实现。

暴力算法

  通过暴力枚举每个子串（ O(n^{2}) ）,再对每个子串进行回文串判定（ O(n) ），可知暴力算法有着O(n^{3})的复杂度。

  我们也可以遍历字符串中每个字符（ O(n) ），以每个字符为回文中心，向字符串两端扩张，判断该回文中心的最大长度（ O(n) ）。这种方式有着 O(n^{2}) 的复杂度，显然优于直接暴力，马拉车算法也是基于这种思想的。

Manacher(马拉车)算法

  1.使用一个 Dist 数组维护字符串中以每个字符为回文中心所得到的最长回文字串的长度半径（如 “abcba” 的长度半径为 3 ）。

  2.利用已求得的 Dist 数组中的信息，通过回文串的对称性直接求得部分回文串，以减少算法的复杂度。

算法介绍

  首先，回文串可以分为奇数长度的回文串（如 “abcba” ）和偶数长度的回文串（如 “abba” ）。在奇回文串中，回文串的对称中心是一个具体的字符（如 “abcba” 中的 “c” ）。而在偶回文串中，回文串的对称中心是两个字符中间的间隔，不再是一个具体的字符。显然，这会影响到我们对称中心的选择。

  所以我们可以通过在字符间增加间隔符，来人为地使所有回文串变成奇回文串，如下：

  我们在字符串 “abcba” 的前后以及每个字符的中间添加字符“#”，得到

    abcba -> #a#b#c#b#a#

  同时我们也可以在字符串的前后添加开始和结束符号（这里使用 “[” 与 “]” ），这样也可以避免数组边界的判断，美化代码。

    #a#b#c#b#a#->[#a#b#c#b#a#]

  通过以上操作，我们使得字符串中仅存在奇回文串了，接下来开始正式介绍马拉车算法。

  首先我们需要 L 与 R 作为标记，记录当前已知的最长的回文子串。初始我们令 Dist[1]=1、L=1、R=1，而在遍历每个字符作为回文中心时，该中心（用 str[i] 表示）与 L 和 R 会存在两种情况：

 1.i>R

  在这种情况中，我们无法利用已知的最长回文串获得任何与 str[i] 相关的对称信息，只能以在i周围暴力寻找最长回文串。

 2.i<=R

  此时， str[i] 与当前最长回文串重合，则我们通过对称性可以知道 Dist[i] \leq Dist[L+R-i]（ L+R-i 即 i 关于当前最长回文子串的中心的对称点）。此处存在小于的情况，是因为如果 Dist[L+R-i] 超出了当前最长回文字串的范围，则无法保证未探索部分的对称性，所以 Dist[i] 实际上是 Dist[i]=MIN(ans[l+r-i],r-i+1)。

  通过遍历字符串，我们只需维护最大的 Dist[i] 的值，就可以知道最长的回文字串的长度了。

完整代码

int Manacher(string str){
    vector<int> ans;
    int len=str.length(),l=1,r=1,MAX=0;
    //添加间隔符，令字符串只存在奇长度回文子串 
    str.resize(2*len+3),ans.resize(2*len+3,1);
    for(int i=2*len+2;i>=1;i--){
        str[i]=i&1?'#':str[i/2-1];
    }
    str[0]='[',str[2*len+2]=']';
    //计算以每个字符中心得到的最长回文字串
    for(int i=1;i<=2*len+2;i++){
        //根据回文的对称性，避免重复计算 
        if(i<=r){
            ans[i]=min(ans[l+r-i],r-i+1);
        }
        //扩张未探索区域 
        while(str[i-ans[i]]==str[i+ans[i]]){
            ans[i]++;
        }
        //更新最长回文串
        if(i+ans[i]>=r){
            l=i-ans[i]+1,r=i+ans[i]-1;
        }
        MAX=max(MAX,ans[i]-1);
    }
    return MAX;
}

【模板】manacher 算法