0%

Posted on In ,

最短回文串

image1

假设原字符串是由$s+s’$组成的，其中$s$是回文字符串，那么我们只需在前面加上$s’$的翻转字符串就可得到回文串$reversed(s’)+s+s’$。为了得到最短的回文串，那么我们必须使得$s$尽可能的长。

如何得到最长的$s$，暴力方法就是枚举$s$并判断是否为回文字符串，时间复杂度为$O(n^2)$，会超时。我们可以考虑利用KMP算法的思想，对于这样一个字符串$str$+’#’+$reversed(str)$，我们使用KMP算法得到它的$fail$数组，即公共前后缀的大小。例如字符串$abac$#$caba$，那么字符串最后一位对应的$fail$数组的值为3，即公共前后缀大小为3，我们可以发现这个3也就是原字符串$abac$中最长的回文串$s$的大小。因为对于原字符串中的$s$来说，由于它是回文串，那么经过翻转之后也和原来一样，同时经过翻转之后它是$reversed(str)$的后缀，同时$s$是$str$的前缀，所以问题就变成了求$str$+#+$reversed(str)$的公共前后缀问题。KMP即可解决。

1
class Solution {
2
    public String shortestPalindrome(String s) {
3
        String ss = s + '#' + new StringBuilder(s).reverse();
4
        int n = s.length();
5
        int[] fail = new int[2*n+1];
6
        Arrays.fill(fail, -1);
7
        for(int i=1; i<2*n+1; i++){
8
            int j = fail[i-1];
9
            while(j!=-1 && ss.charAt(j+1)!=ss.charAt(i)){
10
                j = fail[j];
11
            }
12
            if(ss.charAt(j+1) == ss.charAt(i)){
13
                fail[i] = j+1;
14
            }
15
        }
16
        int maxlen = fail[2*n];
17
        StringBuilder ans = new StringBuilder(s.substring(maxlen+1,n)).reverse();
18
        ans.append(s);
19
        return ans.toString();
20
    }
21
22
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。