题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

样例

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

算法1

马拉车算法 $O(N)$

此题的数据范围不需要使用马拉车算法，但是最好还是学习一下这种算法~

参考文献

参考 Acwing.139回文子串的最大长度
B站讲解视频 wnjxyk的讲解

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        //马拉车算法
        int ans = 0, index;  //ans记录最大长度， index记录最大回文串的中心
        string res = "";
        int n = s.size();
        if(n<=1) return s;
        vector<int> p(5*n,0);
        int rt = 0, mid = 0;
        string str = "$#";
        for(int i = 0; i<n; i++){
            str += s[i];
            str += '#';
        }

        int m = str.size();
        str+= '*';

        for(int i = 1; i<=m; i++){
            p[i] = i<rt? min(p[2*mid-i], rt-i):1;
            while(str[i+p[i]] == str[i-p[i]]) p[i]++;
            if(i+p[i]>rt){
                mid = i;
                rt = i+p[i];
            }
            if(p[i] - 1 >ans){
                ans = p[i] - 1;
                index = i;
            }
        }

        //找到答案
        for(int i = index-ans+1; i<index; i++){
            if(str[i] != '#') res += str[i];
        }
        string t = res;
        reverse(t.begin(),t.end());
        if(str[index] == '#') res = res + t;
        else res = res + str[index] + t;
        return res;
    }
};