214. 最短回文串

214. 最短回文串

原始题目链接：https://leetcode.cn/problems/shortest-palindrome/

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = “aacecaaa”
输出：“aaacecaaa”
示例 2：

输入：s = “abcd”
输出：“dcbabcd”

提示：

0 <= s.length <= 5 * 104
s 仅由小写英文字母组成

解题思路：

使用字符串哈希算法，找到s的最长前缀回文子串，找的方式是使用哈希算法，计算前缀子串和反序前缀子串的哈希值是否相等，相等就是回文串。题目要求的是需要添加的字符串，就是s-s的最长前缀子串。
需要记住两个公式：
#s的前缀串的哈希值公式
left = (left * base + ord(s[i])) % mod
#s的反序前缀串哈希值公式
right = (right + mul * ord(s[i])) % mod

代码实现：

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        # 设置base计算哈希值，设置模为了哈希值的结果表示在一个可控的范围
        base, mod = 131, 10**9 + 7
        # left表示前缀哈希值，right表示反序前缀哈希值
        left = right = 0

        # 存储base的幂
        mul = 1
        # s中最长的回文串对应在s的下标，初始化为-1
        best = -1
        
        # 从s的头开始查找
        for i in range(n):
            # s的前缀串的哈希值公式
            left = (left * base + ord(s[i])) % mod
            # s的反序前缀串哈希值公式
            right = (right + mul * ord(s[i])) % mod

            # 如果哈希值相等表示是回文串
            if left == right:
                best = i
            # 更新幂
            mul = mul * base % mod
        # s - s的最长回文前缀串的反序串，就是要添加的字符串
        add = ("" if best == n - 1 else s[best+1:])
        
        return add[::-1] + s

参考文献：
https://leetcode.cn/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/