LeetCode：最短回文串

题意

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

Solution

等价于求字符串 $s$ 以 $s_0$ 开头的最长回文串，然后多出来的后缀翻转后就是需要补足的最小长度，判断回文可以采用哈希。

Code

class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        long left = 0, right = 0, base = 13331, mod = 1000000007, pre = 1;
        int pos = -1;
        for (int i = 0; i < n; i++) {
            left = (left * base + s.charAt(i)) % mod;
            right = (right + pre * s.charAt(i)) % mod;
            if (left == right) {
                pos = i;
            }
            pre = pre * base % mod;
        }
        String add = (pos == n-1 ? "" : s.substring(pos+1,n));
        StringBuilder res = new StringBuilder(add).reverse();
        res.append(s);
        return res.toString();
    }
}