5 Longest Palindromic Substring 最長(zhǎng)回文子串

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

Example:

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

題目描述:
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 :

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

思路:

馬拉車(chē)算法(Manacher's Algorithm)
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        if (s.size() < 2) return s;
        string t = "$#";
        for (int i = 0; i < s.size(); i++)
        {
            t += s[i];
            t += '#';
        }
        t += '*';
        int mid = 0, right = 0, result_index = 0, temp[t.size()]{0};
        for (int i = 0; i < t.size(); i++) temp[i] = 1;
        for (int i = 1; i < t.size() - 1; i++)
        {
            if (right > i) temp[i] = min(temp[2 * mid - i], right - i);
            while (t[i + temp[i]] == t[i - temp[i]]) ++temp[i];
            if (right < i + temp[i])
            {
                right = i + temp[i];
                mid = i;
            }
            if (temp[i] > temp[result_index]) result_index = i;
        }
        int result_length = temp[result_index] - 1;
        result_index -= temp[result_index];
        result_index /= 2;
        return s.substr(result_index, result_length);
    }
};

Java:

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        StringBuilder sb = new StringBuilder("$#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        sb.append('*');
        int mid = 0, right = 0, resultIndex = 0, temp[] = new int[sb.length()];
        for (int i = 0; i < sb.length(); i++) temp[i] = 1;
        for (int i = 1; i < sb.length() - 1; i++) {
            if (right > i) temp[i] = Math.min(temp[2 * mid - i], right - i);
            while (sb.charAt(i + temp[i]) == sb.charAt(i - temp[i])) ++temp[i];
            if (right < i + temp[i]) {
                right = i + temp[i];
                mid = i;
            }
            if (temp[i] > temp[resultIndex]) resultIndex = i;
        }
        int resultLength = temp[resultIndex] - 1;
        resultIndex -= temp[resultIndex];
        resultIndex /= 2;
        resultLength += resultIndex;
        return s.substring(resultIndex, resultLength);
    }
}

Python:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = '$#'
        for i in range(len(s)):
            t += s[i]
            t += '#'
        t += '*'
        temp = [1] * len(t)
        mid = 0
        right = 0
        result_index = 0
        for i in range(1, len(t) - 1):
            if right > i:
                temp[i] = min(temp[2 * mid - i], right - i)
            while t[i + temp[i]] == t[i - temp[i]]:
                temp[i] += 1
            if right < i + temp[i]:
                right = i + temp[i]
                mid = i
            if temp[i] > temp[result_index]:
                result_index = i
        result_length = temp[result_index] - 1
        result_index -= temp[result_index]
        result_index //= 2
        result_length += result_index
        return s[result_index:result_length]