回文子串问题之Manacher算法

短命女 2022-05-09 23:22 202阅读 0赞

#### 写在前面 ####

回文子串问题。

#### 题目简述 ####

> 时间限制:1000ms  
> 单点时限:1000ms  
> 内存限制:256MB  
> 描述  
> 小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。  
> 这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？” 小Ho奇怪的问道：“什么叫做最长回文子串呢？”  
> 小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”  
> 小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？  
> 小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。”

#### 解法 ####

最长回文子串问题有多种解法。

*  暴力解法：遍历每一元素再由其为中心向两边判断是否为回文串 时间复杂度为o(n^2)
 *  动态规划解法：开一个二维数组dp\[i\]\[j\]表示子串i-j是否为回文子串。当将表填满的时候只需要计算dp\[i\]\[j\]当中为1的情况下最大的j-i+1的值就是最长的回文子串的长度。而状态转移方程为：  
    ![在这里插入图片描述][452750-20161030112606812-2106192201.png]  
    动态规划的问题在于空间时间复杂度都为o(n^2)并没有很好的解决问题。
 *  Manacher马拉车算法：可以将问题在o(n)的时间和空间复杂度上解决。

回文子串的问题就在于对于每一个元素的考虑总会产生重复计算，如果仅仅按照每个元素作为中心的确问题被拆分成n个子问题，对于每个可能的中心都需要o(n)的时间复杂度得到以其为中心的回文串的最大长度，对与下一个需要遍历的情况来说上一次的计算并没有带来任何的有用信息，导致每次计算都得从中心向两边一个个判断是否相等。

仔细想想难道真的没有可用信息了么？  
其实不然，当计算过i点为中心的回文串的长度之后，对于后面位置来说，如果他在i点的最长回文串的内部，那么我们可以利用次信息做文章。具体的证明在别的博客里说的很详细我会在后面贴出。这里我只说我自己的理解，毕竟这样的算法不是说很容易就能够思考的出来的，重点还是在于其中内在的规律。

#### 我的理解 ####

最长回文子串的问题，烦就烦在时间复杂度上，对于问题的建模很容易就会想到应该以每个元为中心的可能上入手，如果以每个元素为起点那么问题就麻烦了。那么前面的计算到底怎么能够被后面利用，到底是该用动态规划的想法去存储中间结果还是应该怎么做呢？如果从0开始去设计是非常难的，毕竟想出这算法的人都是研究了很久的，也正是可以借助他们的想法我们才得以总结。很显然，回文回文，最重要的就是对称性！ 没有了对称也就不是回文，所以牢牢抓住对称性才是这个问题的核心。一个回文串的计算包括这样几个部分，找到回文中心，从中心向两边逐个判断是否对称相等，直到延伸到最大回文长度为止。**此中唯一的计算就是判断是否相等的过程，对于一个位置的元素可能被判断几次相等的操作也就是最终复杂度的来源。** 显然，暴力解当中对于每一个位置的元素都有可能被其他的元素作为中心找回文的时候拿出来比较一次，那么对于n个元素自然比较次数的最坏情况就是 n^2了。如果说能够将算法时间复杂度降到O(n)，那么自然每个位置的元素只应该拿出被比较O(1)次。说道这，马拉车算法的核心就已经出来了。

由于回文串的对称性，对于一个大回文串当中的位置来说，由于遍历顺序我们在大回文串中心后面遍历到的位置的元素可以直接找到该位置在大回文串当中的对称位置的情况作为基础，而不是直接的从0开始计算，具体的就看下面的篇博客吧~说的还是很详细的。  
[Manacher算法][Manacher]

#### 马拉车算法代码 ####

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    //最长回文子串解法：马拉车算法
    int Manacher(string& s) {
        
        int res = 1;
        int n = s.size();
        if(n==1) return 1;
        if(n==0) return 0;
    
    //字符串预处理
        string str;
        for(int i=0;i<n;++i) {
        
            str += "#";
            str += s[i];
        }
        str += "#";
    //马拉车算法核心
        vector<int> len(str.size(),1);
        int id = 0, max_l = 1;
    
        for(int i=0;i<len.size();++i) {
        
            if(i < id + max_l) {
        
                len[i] = min(len[2*id - i],id + max_l - i);
            }
            int l = i - len[i],r = i + len[i];
            while(l>=0&&r<len.size()) {
        
                if(str[l]==str[r])
                    ++len[i];
                else
                    break;
                --l;
                ++r;
            }
            if(i+len[i]>id+max_l) {
        
                id = i;
                max_l = len[i];
            }
            res = max(len[i]-1,res);
        }
        return res;
    }
    
    int main() {
        
        int n;
        cin >> n;
    
        vector<string> v;
        for(int i=0;i<n;++i) {
        
            string s;
            cin >> s;
            v.push_back(s);
        }
    
        for(auto each : v) {
        
            cout << helper(each) << endl;
        }
    
        return 0;
    }

[452750-20161030112606812-2106192201.png]: /images/20220510/ed9b3c45a2974464a6adc95d1e56316f.png
[Manacher]: https://segmentfault.com/a/1190000008484167