5, 最长回文子串

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring

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

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"

Manachers算法

• Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s is None or len(s) == 0 or len(s) == 1:
            return s

        temp = handle_arg(s)
        length = len(temp)
        center = 0
        right = 0
        arr = [0] * length

        max_length = 0
        max_index = 0

        for i in range(1, length - 1):
            j = 0
            if i <= right:
                j = min(right - i, arr[2 * center - i])

            while temp[i - j - 1] == temp[i + j + 1]:
                j += 1

            if i + j > right:
                center = i
                right = i + j

            arr[i] = j
            if j > max_length:
                max_length = j
                max_index = i

        left_index = (max_index - max_length) // 2
        return s[left_index: left_index + max_length]


def handle_arg(s: str):
    result = '^'
    for item in s:
        result += '#' + item
    result += '#$'
    return result

• Go

func longestPalindrome(s string) string {
    temp := handleArg(s)
    length := len(temp)
    center := 0
    right := 0

    arr := make([]int, length)

    maxLength := 0
    maxIndex := 0

    for i := 1; i < length-1; i++ {
        j := 0
        if i <= right {
            j = min(right-i, arr[2*center-i])
        }

        for temp[i-j-1] == temp[i+j+1] {
            j++
        }

        if i+j > right {
            center = i
            right = i + j
        }

        arr[i] = j
        if j > maxLength {
            maxIndex = i
            maxLength = j
        }
    }

    leftIndex := (maxIndex - maxLength) / 2
    return s[leftIndex : leftIndex+maxLength]
}

func handleArg(s string) string {
    var result bytes.Buffer
    result.WriteString("^")
    for _, i := range s {
        result.WriteString("#")
        result.WriteString(string(i))
    }
    result.WriteString("#$")
    return result.String()
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

• Java

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) {
            return s;
        }

        String temp = handleArg(s);
        char[] chars = temp.toCharArray();
        int length = chars.length;
        int center = 0, right = 0;
        int[] arr = new int[length];

        int maxLength = 0;
        int maxIndex = 0;

        for (int i = 1; i < length - 1; i++) {
            int j;
            if (i <= right) {
                j = Math.min(right - i, arr[2 * center - i]);
            } else {
                j = 0;
            }

            while (chars[i - 1 - j] == chars[i + 1 + j]) {
                j++;
            }

            if (i + j > right) {
                center = i;
                right = i + j;
            }

            arr[i] = j;
            if (j > maxLength) {
                maxLength = j;
                maxIndex = i;
            }
        }

        int leftIndex = (maxIndex - maxLength) / 2;
        return s.substring(leftIndex, leftIndex + maxLength);
    }

    private String handleArg(String s) {
        StringBuilder result = new StringBuilder("^");
        for (int i = 0; i < s.length(); i++) {
            result.append("#").append(s.charAt(i));
        }
        return result.append("#&").toString();
    }

}