题目描述

最长回文子串

样例

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

两种暴力法
一种动态规划
一个马拉车

算法1

(直接暴力枚举) $O(n^2)$

暴力法，直接取每个字串然后判断是否为回文串，会超时

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        string str;
        int maxlength=0;
        if(s.empty()) return str;
        for(auto i = s.begin(); i < s.end(); ++i){
            for(auto j = i+1; j <= s.end(); ++j){
                string temp(i,j);
                if(checkit(temp)==true){
                    if(maxlength < temp.size()){
                        maxlength = temp.size();
                        str = temp;
                    }
                }
            }
        }
        return str;
    }
    bool checkit(string t){
        vector<char> vc;
        for(auto c : t){
            vc.push_back(c);
        }
        for(auto i = 0; i<vc.size(); ++i){
            if(vc[i]!=vc[vc.size()-1-i]){
                return false;
            }
        }
        return true;
    }
};

算法2

(分奇偶暴力枚举) $O(n^2)$

以字符为中心，向两边搜索，分奇数串和偶数串两种情况O（n²），可以通过

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        int strstart,curlen;
        int maxlength;
        int slen = s.size();
        string str;
        if(s.empty()) return str;
        maxlength = 1;  //最长回文串长度
        strstart = 0;   //最长回文串起点
        for(auto i = 0; i < slen; ++i){
            //奇数长度的字符串
            int left = i -1, right = i + 1;
            while(left >= 0 && right < slen && s[left]==s[right]){
                curlen = right - left + 1;
                if(curlen > maxlength){
                    strstart = left;
                    maxlength = curlen;
                }
                --left;
                ++right;
            }
            //偶数长度的字符串
            left = i;
            right = i + 1;
            while(left >= 0 && right < slen && s[left]==s[right]){
                curlen = right - left + 1;
                if(curlen > maxlength){
                    strstart = left;
                    maxlength = curlen;
                }
                --left;
                ++right;
            }
        }
        str = s.substr(strstart,maxlength);
        return str;
    }
};

算法3

(动态规划) $O(n^2)$

参考

https://blog.csdn.net/shineboyxxb/article/details/52079360

【fill_n】
fill_n函数的作用是：给一个起始点，然后再给你一个数值count和val。把从起始点开始依次赋予count个元素val的值。
注意： 不能在没有元素的空容器上调用fill_n函数

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        int strstart, maxlength, curlen;
        int slen = s.size();
        string str;
        if(s.empty()) return str;

        bool dp[slen][slen];
        fill_n(&dp[0][0], slen*slen, false);


        maxlength = 1;
        strstart = 0;
        for(auto i = 0; i < slen; ++i){
            for(auto j = 0; j <= i; ++j){
                //dp[j][i]表示从j到i是否为回文字符串
                if(i - j < 2){
                    dp[j][i] = (s[i]==s[j]);
                }else{
                    dp[j][i] = (s[i]==s[j] && dp[j+1][i-1]);
                }
                curlen = i - j + 1;
                if(dp[j][i] && curlen > maxlength){
                    strstart = j;
                    maxlength = curlen;
                }
            }
        }
        str = s.substr(strstart,maxlength);
        return str;
    }
};

算法3

(manacher) $O(n)$

参考

https://www.cnblogs.com/love-yh/p/7072161.html
(解释的较清楚，但示意图和代码在半径及算上不对应，示意图算上中心了，代码中没有算)

https://blog.csdn.net/han_xiaoyang/article/details/11969497#t20
（示意图和代码在半径计算上对应，都没有计算中心的个数）

【manacher】

加入符号，使字符串变为奇数长度（无论奇偶变后都是奇数长度）。S = “abaaba”, T = “#a#b#a#a#b#a#”
p[i]存的是i为中心的回文串的半径，不含i位置。
T = # a # b # a # a # b # a #
p = 0 1 0 3 0 1 6 1 0 3 0 1 0
用已知右边界最远的串帮助当前位置进行判断。

【 s.substr(pos, n) 】
用途：一种构造string的方法
形式：s.substr(pos, n)
解释：返回一个string，包含s中从pos开始的n个字符的拷贝（pos的默认值是0，n的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
补充：若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        int slen = s.size();
        string str;
        if(s.empty()) return str;
        string T = "#";
        //参考网页中在T最开始多加一个其他字符作为不等的终止，这个程序里没采用这个方法，这个是靠while里判断防止出界的
        for(auto c:s){
            T = T + c;
            T = T + "#";
        }
        vector<int> p(T.size(),0);
        //p[i]存的是i为中心的回文串的半径，不含i位置。
//         T = # a # b # a # a # b # a #
//         p = 0 1 0 3 0 1 6 1 0 3 0 1 0
        int center = 0, right = 0; 
        //记录半径到达最远的中心的索引，和右边界的索引
        for(auto i = 1; i < T.size(); ++i){
            //i关于最长回文串中心位置的对称点
            int i_mirror = 2*center - i;
            //判断当前计算的位置i是否在已知的最长回文串内，如果不是p[i]=0；
            //如果是的话分两种情况
            //一种是以i_mirror为中心的回文串在最长回文范围内p[i_mirror]<right-i，那由对称性p[i]至少为p[i_mirror]
            //另一种是以i_mirror为中心的回文串不在最长回文范围内p[i_mirror]>right-i,那由对称性p[i]至少为right-i，即能够一直到边界right处。
            p[i] = (right > i)? min(right-i , p[i_mirror]) : 0;

            while(i-p[i]-1>=0 && i+p[i]+1<T.size() && T[i - p[i] -1]== T[i + p[i] + 1]){
                ++p[i];
            }
            //注意，这儿不是因为p[i]的值大才更新，而是看之后计算的位置再哪个字符串的覆盖之下，即按右边界到达最远进行更新
            if(i + p[i] > right){
                center = i;
                right = i + p[i];
            }           
        }
        //找到最大半径和对应中心；
        int maxlen = 0;
        int maxcenter = 0;
        for(auto i = 0; i < T.size(); ++i){
            if(p[i] > maxlen){
                maxlen = p[i];
                maxcenter = i;
            }
        }
        //T中回文的半径就是原字符串s回文的长度，因为T中回文串长度tlen=2*slen+1，slen为s中对应回文串长度；
        //而同样2*p[i]+1=tlen；所以p[i]=slen；
        //T中最长回文左边界（起始索引） tleft=maxcenter-maxlen
        //由T的构造可知，左边界对应的一定是一个#，真正的字符边界为左边界的#右边一位的字符，即索引tleft+1对应的字符
        //t中坐标与s中索引关系为 tindex = 2 * sindex + 1；
        //所以T中最长回文对应回s中的最长回文起始处为 tleft+1 = sleft * 2 +1 ；解的sleft = tleft/2
        str = s.substr((maxcenter-maxlen)/2, maxlen);
        return str;
    }
};