5. Longest Palindromic Substring

问题

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思路

最长回文子串，很经典的题。
思路一：自己想的话就是枚举字符串的中心，然后判断，时间复杂度O(n^2)。
思路二：Manacher算法，时间复杂度O(n)。
参考 https://segmentfault.com/a/1190000003914228

实现

class Solution {
public:
    string longestPalindrome(string s) {
        const int MAX_STR = 1005;
        string str;
        for(int i=0; i<s.size(); i++){
            str.append("#");
            str.append(s, i, 1);
        }
        str.append("#");
        
        int pos=0, MaxRight=0, RL[MAX_STR*2+1]={0};
        for(int i=0; i<str.size(); i++){
            int j;
            if(i<MaxRight){
                j=min(RL[2*pos-i], MaxRight-i);
            }
            else{
                j=1;
            }
            while(i+j<str.size() && i-j>=0 && str[i-j]==str[i+j]){
                j++;
            }
            RL[i]=j;
            if(i+j-1>MaxRight){
                pos = i;
                MaxRight = i+j-1;
            }
        }
        int maxi=0, maxRL=0;
        for(int i=0; i<str.size(); i++){
            if(RL[i]>maxRL){
                maxRL = RL[i];
                maxi = i;
            }
        }
        return s.substr((maxi-maxRL+1)/2, maxRL-1);
    }
};

思考

主要是学习Manacher算法
并且熟悉string的相关操作