【LeetCode】5. Longest Palindromic Substring

题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
求最长回文子串问题

方法一：暴力

我们可以遍历每一个子串，并检测该子串是否为回文串，最后得出最长的一个回文子串，但这种方法的时间复杂度会达到\(O(n^3)\)，在LeetCode上提交将会TLE

方法二：中心扩散法

这种方法的时间复杂度将会被优化至\(O(n^2)\)，但本质上也是暴力，该算法思想如下：

• 选择字符串中的某一个点或两个点作为回文子串的中心（选两个点是因为偶数长度的回文串）

• 使用两个指针，从中心往两边扩散，知道两个指针指向的字符不再相等为止

• 通过两个指针可以返回该回文子串的长度

• 获取最长回文子串的长度，即可通过运算得到回文子串的起始点，调用substr函数返回该子串

class Solution {
public:
    int helper(string A, int n, int L, int R) {
        int left = L ;
        int right = R ;
        while (left >= 0 && right < n && A[left] == A[right]) {
            left -- ;
            right ++ ;
        }
        return right - left - 1 ;
    }
    string longestPalindrome(string s) {
        int n = s.size() ;
        int maxLen = 1 ;
        int start = 0 ;
        for (int i = 0;i < s.size();i++) {
            // helper(s, n, i,i) 选择一个点作为中心
            // helper(s, n, i,i + 1) 选择两个点作为中心
            int len = max(helper(s, n, i,i), helper(s, n, i, i + 1)) ;
            if (maxLen < len) {
                maxLen = len ;
                start = i - (int)((len - 1) / 2) ;
            }
        }
        return s.substr(start, maxLen) ;
    }
};

方法三：Manacher

使用Manacher算法（马拉车），Manacher算法本质上还是中心扩散法，但是利用了之前已经判定过的回文子串的数据，减少了重复遍历的过程

（关于Manacher：https://zhuanlan.zhihu.com/p/88299272）

class Solution {
public:
    int min(int a, int b) {
        return a > b ? b : a ;
    }
    string createNewString(string A) {
        string s ;
        for (unsigned int i = 0;i < A.size();i++) {
            s.append("#") ;
            s.append(1, A[i]) ;
        }
        s.append("#") ;
        return s  ;
    }
    string manacher(string A) {
        int len = A.size() ;
        if (len < 2){
            return A ;
        }
        string s = createNewString(A) ;
        len = s.size() ;
        vector<int> p(len, 0) ;
        int maxRight = 0 ;
        int center = 0 ;
        int maxlen = 1 ;
        int start = 0 ;
        for (unsigned int i = 0;i < len;i++) {
            if (i < maxRight) {
                int mirror = 2 * center - i ;
                p[i] = min(p[mirror], maxRight - i)  ;
            }
            int left = i - 1 - p[i] ;
            int right = i + 1 + p[i] ;
            while (left >= 0 && right < len && s[left] == s[right]) {
                p[i] ++ ;
                left --;
                right ++ ;
            }
            if (i + p[i] > maxRight) {
                maxRight = i + p[i] ;
                center = i ;
            }
             
            if (p[i] > maxlen) {
                maxlen = p[i] ;
                start = (i - maxlen) / 2 ;
            }
             
             
        }
        return A.substr(start, maxlen) ;
    }
    string longestPalindrome(string s) {
        return manacher(s) ;
    }
};

【LeetCode】5. Longest Palindromic Substring

原文：https://www.cnblogs.com/Suans/p/14597492.html