[算法系列之七]Manacher算法之最大回文子串

你的名字 2023-05-31 02:42 16阅读 0赞

回文串定义：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。  
回文子串，顾名思义，即字符串中满足回文性质的子串。

经常有一些题目围绕回文子串进行讨论，比如  HDOJ\_3068\_最长回文，求最长回文子串的长度。朴素算法是依次以每一个字符为中心向两侧进行扩展，

显然这个复杂度是 O(N^2)的，关于字符串的题目常用的算法有 KMP、后缀数组、 AC 自动机，这道题目利用扩展 KMP可以解答，其时间复杂度也很快 O(N\*logN)。

但是，今天笔者介绍一个专门针对回文子串的算法，其时间复杂度为 O(n)，这就是 manacher 算法。

大家都知道，求回文串时需要判断其奇偶性，也就是求 aba 和 abba 的算法略有差距。然而，这个算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考  
虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘\#’或者‘$’等字符。例如：  
原串：abaab  
新串：\#a\#b\#a\#a\#b\#  
这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘\#’为中心的奇数回文串了。  
接下来就是算法的中心思想，用一个辅助数组 P 记录以每个字符为中心的最长回文半  
径，也就是 P\[i\]记录以 Str\[i\]字符为中心的最长回文串半径。 P\[i\]最小为 1，此时回文串为 Str\[i\]本身。  
我们可以对上述例子写出其 P 数组，如下   
新串：  \#   a   \#   b   \#   a   \#   a   \#   b   \#  
P\[\]  :     1    2   1   4   1   2   5   2   1   2   1  
我们可以证明 P\[i\]-1 就是以 Str\[i\]为中心的回文串在原串当中的长度。  
证明：  
1、显然 L=2\*P\[i\]-1 即为新串中以 Str\[i\]为中心最长回文串长度。  
2、以 Str\[i\]为中心的回文串一定是以\#开头和结尾的，例如“\#b\#b\#”或“\#b\#a\#b\#”所以 L 减去最前或者最后的‘\#’字符就是原串中长度的二倍，即原串长度为(L-1)/2，化简  
的 P\[i\]-1。得证。

依次从前往后求得 P 数组就可以了，这里用到了 DP(动态规划)的思想，也就是求 P\[i\]的时候，前面的 P\[\]值已经得到了，我们利用回文串的特殊性质可以进行一个大大的优化。

核心代码：

// MaxId为i字符之前最大回文串向右延伸的最大位置
        // id为MaxId对应的最大回文串的中心位置
        for(int i = 1;i < len;i++){
            //初步定i位置字符为中心的半径
            if(MaxId > i){
                p[i] = min(MaxId - i,p[2*id - i]);
            }
            else{
                p[i] = 1;
            }
            //继续确定i位置字符为中心的半径 这地方用到'$'
            while(str[i-p[i]] == str[i+p[i]]){
                p[i]++;
            }
            //更新MaxId,id
            if(p[i]+i > MaxId){
                MaxId = p[i] + i;
                id = i;
            }
        }

为了防止求 P\[i\]向两边扩展时可能数组越界，我们需要在数组最前面和最后面加一个特殊字符，令 P\[0\]= ‘$’最后位置默认为‘\\0’不需要特殊处理。此外，我们用 MaxId 变量  
记录在求 i 之前的回文串中延伸至最右端的位置，同时用 id 记录取这个 MaxId 对应回文串的中心位置。  
通过下面这句话，算法避免了很多没必要的重复匹配。

if(MaxId>i)
    {
    p[i]=min(p[2*id-i],MaxId-i);
    }

那么这句话是怎么得来的呢，其实就是利用了回文串的对称性，如下图，

![SouthEast][]

j=2\*id-i 即为 i 关于 id 的对称点，根据对称性，P\[ j\]的回文串也是可以对称到 i 这边的,但是如果 P\[ j\]的回文串对称过来以后超过 MaxId 的话，超出部分就不能对称过来了，如下  
图，所以这里 P\[i\]为的下限为两者中的较小者，p\[i\]=Min(p\[2\*id-i\],MaxId-i) 。

![SouthEast 1][]

算法的有效比较次数为 MaxId 次，所以说这个算法的时间复杂度为 O(n)。

这是我具体实现的代码：

#include <string.h>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    //数据预处理
    char* Init(char* s){
        int len = strlen(s);
        char* str = new char(2*len+4);
        str[0] = '$';
        int index = 1;
        for(int i = 0;i < len;i++){
            str[index++] = '#';
            str[index++] = s[i];
        }
        str[index++] = '#';
        str[index] = '\0';
        return str;
    }
     
    string MaxPalindromeNumber(char* s){
        char *str = Init(s);
        int maxId = 0,center = 1;
        int len = strlen(str);
        int *p = new int[len+1];
     
        // MaxId为i字符之前最大回文串向右延伸的最大位置
        // id为MaxId对应的最大回文串的中心位置
        for(int i = 1;i < len;i++){
            //初步定i位置字符为中心的半径
            if(maxId > i){
                p[i] = min(maxId - i,p[2*center - i]);
            }
            else{
                p[i] = 1;
            }
            //继续确定i位置字符为中心的半径 这地方用到'$'
            while(str[i-p[i]] == str[i+p[i]]){
                p[i]++;
            }
            //更新MaxId,id
            if(p[i]+i > maxId){
                maxId = p[i] + i;
                center = i;
            }
        }
        // 最大长度
        int maxLen = 0;
        center = 1;
        for(int i = 1;i < len;i++){
            if(str[i] != '#' && p[i] - 1 > maxLen){
                maxLen = p[i] - 1;
                center = i;
            }
        }
        //提取最大回文串
        char* maxStr = new char[maxLen+1];
        int index = 0;
        for(int i = center - maxLen;i <= center + maxLen;i++){
            if(str[i] != '#'){
                maxStr[index++] = str[i];
            }
        }
        maxStr[index] = '\0';
        return maxStr;
    }
     
    int main(){
    	char* str="skjflkdsjfkldsababasdlkfjsdwieowowwpw";
    	cout<<MaxPalindromeNumber(str);
    	return 0;
    }

![SouthEast 2][]

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/40380947][https_blog.csdn.net_SunnyYoona_article_details_40380947]

[SouthEast]: /images/20230531/982580ced34145d08397724e1aa38f43.png
[SouthEast 1]: /images/20230531/96e2c95841dd408aa98fdefe80f6ab0c.png
[SouthEast 2]: /images/20230531/861ccb1877d94a6894ac5e6ff06cd352.png
[https_blog.csdn.net_SunnyYoona_article_details_40380947]: https://blog.csdn.net/SunnyYoona/article/details/40380947