【leetcode】5. Longest Palindromic Substring最长回文子串

class Solution:

    def longestPalindrome(self, s: str) -> str:

        n = len(s)

        Max,sub = 0,s[0:1]

        for i in range(n):

            tmp = self.searchPalindrome(i-1,i+1,s)

            if len(tmp) > Max:

                Max = len(tmp)

                sub = tmp

            tmp = self.searchPalindrome(i-1,i,s)

            if len(tmp) > Max:

                Max = len(tmp)

                sub = tmp    

        return sub

    

    def searchPalindrome(self, left: int, right: int, s: str) -> int:

        sub = ""

        while left != -1 and right != len(s):

            if s[left] == s[right]:

                sub = s[left:right+1]

                left-=1

                right+=1

            else : break

        return sub

class Solution:

    # Manacher 算法

    def longestPalindrome(self, s: str) -> str:

        # 特判 

        if len(s) < 2 or s == s[::-1]:

            return s



        # 得到预处理字符串

        t = "#" + "#".join(s) + "#"



        # 新字符串的长度

        t_len = len(t)



        # 数组 p 记录了扫描过的回文子串的信息

        p = [0]*t_len



        # 双指针，它们是一一对应的，须同时更新

        max_right = 0

        center = 0



        # 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度

        max_len = 1

        # 原始字符串的最长回文子串的起始位置，与 max_len 必须同时更新

        start = 1



        for i in range(t_len):

            if i < max_right:

                mirror = 2 * center - i

                # 这一行代码是 Manacher 算法的关键所在，要结合图形来理解

                p[i] = min(max_right - i, p[mirror])



            # 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中

            left = i - (1 + p[i])

            right = i + (1 + p[i])



            # left >= 0 and right < t_len 保证不越界

            # t[left] == t[right] 表示可以扩散 1 次

            while left >= 0 and right < t_len and t[left] == t[right]:

                p[i] += 1

                left -= 1

                right += 1



            # 根据 max_right 的定义，它是遍历过的 i 的 i + p[i] 的最大者

            # 如果 max_right 的值越大，进入上面 i < max_right 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了

            if i + p[i] > max_right:

                # max_right 和 center 需要同时更新

                max_right = i + p[i]

                center = i



            if p[i] > max_len:

                # 记录最长回文子串的长度和相应它在原始字符串中的起点

                max_len = p[i]

                start = (i - max_len) // 2

        return s[start: start + max_len]