【题解manacher-2】最短回文串-末尾增加字符

描述

给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添加的最短字符串

[举例]

str = "abcd123321"，在必须包含最后一个字符的情况下，最长的回文子串是"123321"，之前不是最长回文子串的部分是'abcd"，所以末尾应该添加的部分就是"dcba"。

[要求]

如果str的长度为N，解决进阶问题的时间复杂度为O(N).

保证输入数据无回文串

输入描述：

输入为一个字符串str

输出描述：

输出一个字符串。

示例1

输入：

abcd123321

输出：

dcba

说明：

添加后的字符串为abcd123321dcba

示例2

输入：

ababab

输出：

备注：

设N表示输入字符串的长度保证输入字符中只含有小写字母及数字1⩽N⩽5∗1051⩽N⩽5∗105

分析只能在字符串末尾增加字符使整个字符串变成最短的回文字符串。也就是在末尾添加最少的字符是字符串变成回文串。

根据manacher算法，详见：【题解manacher-1】最长回文子串的长度。可以知道p[i]=各种以i为中心能找到的最长回文子串的半径，其中包含以字符串s 尾字符为end的所有回文子串，此时R=s.length()。计算当R=s.length()的时候能够出现的最长的回文子串。举例：bcbaaaa，以最后一个字符a结尾的最长回文子串是aaaa，在aaaa后面补充之前的一半字符bcb就构成在末尾添加字符形成的最短回文字符串 bcbaaaabcb。

所以题目转换成：求含字符串s最后1个字符的最长回文子串的长度。

public static String shortestPalindrome(String s) {
    int maxLen=maxLastLcpsLength(s);
    StringBuilder sb=new StringBuilder(s.substring(0,s.length()-maxLen)); //找到前半部分字符串
    return sb.reverse().toString(); //reverse就是答案
}

public static int maxLastLcpsLength(String str) {

        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] s = manacherString(str);
        int[] p = new int[s.length];
        int C = -1;
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < s.length; i++) {
            p[i] = R > i ? Math.min(p[2 * C - i], R - i) : 1;
            //C是中心位置，2*C-i的位置依次对应了C左边已经算出来的p[i],所以不用算了。最小值是C-i
            while (i + p[i] < s.length && i - p[i] > -1 && s[i + p[i]] == s[i - p[i]]) p[i]++;
            if (i + p[i] > R) {
                R = i + p[i];
                C = i;
            }
            if(R==s.length){ //找出当R=s.length时候出现的最长回文子串的p[i]
                max = Math.max(max, p[i]);
            }
            
        }
        return max - 1; //R=s.length时候出现的最长回文子串的长度
    }

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

同系列题目：

【题解manacher-1】最长回文子串的长度

【题解manacher-2】最短回文串-末尾增加字符

【题解manacher-3】leet214 最短回文串--前面增加字符