214. minimum palindrome string

214. The shortest palindrome string

Original title link ：https://leetcode.cn/problems/shortest-palindrome/

Given a string s, You can convert a string to a palindrome string by adding characters in front of it . Find and return the shortest palindrome string that can be converted in this way .

Example 1：

Input ：s = “aacecaaa”
Output ：“aaacecaaa”
Example 2：

Input ：s = “abcd”
Output ：“dcbabcd”

Tips ：

0 <= s.length <= 5 * 104
s It's only made up of lowercase letters

Their thinking ：

Use the string hash algorithm , find s The longest prefix palindrome substring of , The way to find it is to use the hash algorithm , Calculate whether the hash values of prefix substring and reverse prefix substring are equal , Equality is palindrome string . The title requires the string to be added , Namely s-s The longest prefix substring of .
You need to remember two formulas ：
#s The hash value formula of the prefix string of
left = (left * base + ord(s[i])) % mod
#s Inverse prefix string hash value formula
right = (right + mul * ord(s[i])) % mod

Code implementation ：

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        #  Set up base Calculate the hash value , Set the modulus so that the result of the hash value is represented in a controllable range 
        base, mod = 131, 10**9 + 7
        # left Indicates the prefix hash value ,right Indicates the reverse prefix hash value 
        left = right = 0

        #  Storage base The power of 
        mul = 1
        # s The longest palindrome string in corresponds to s The subscript , Initialize to -1
        best = -1
        
        #  from s Start search with the header of 
        for i in range(n):
            # s The hash value formula of the prefix string of 
            left = (left * base + ord(s[i])) % mod
            # s Inverse prefix string hash value formula 
            right = (right + mul * ord(s[i])) % mod

            #  If the hash values are equal, it means that it is a palindrome string 
            if left == right:
                best = i
            #  Update power 
            mul = mul * base % mod
        # s - s The reverse order of the longest palindrome prefix string of , Is the string to be added 
        add = ("" if best == n - 1 else s[best+1:])
        
        return add[::-1] + s

reference ：
https://leetcode.cn/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/