Manacher算法 && Longest && Shortest Palindrome

原创

大学里的混子

修改于 2019-02-22 09:52:51

33300

代码可运行

文章被收录于专栏：LeetCodeLeetCode

运行总次数：0

代码可运行

一、Manacher算法、

public static char[] mannacherString( 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;
    }

public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0){
            return 0;
        }
        char[] charArr = mannacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0;i != charArr.length;i++){
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i],pR - i) :1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1){
                if (charArr[i+pArr[i]] == charArr[i - pArr[i]]){
                    pArr[i]++;
                }else break;
            }
            if ( i + pArr[i] > pR){
                pR = i +pArr[i];
                index = i;
            }
            max = Math.max(max,pArr[i]);
        }
        return max - 1;
    }

二、214.Shortest Palindrome

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

解法：

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

public static String shortestPalindrome(String s) {
    if (s == null || s.length() < 2) return s;
    StringBuffer stringBuffer = new StringBuffer(s);
    stringBuffer.reverse();
    String revStr = new String(stringBuffer);
    char[] chars = manacherStr(revStr);
    System.out.println(chars);
    int pArr [] = new int[chars.length];
    int pR = -1;
    int index = -1;
    int maxContainEnd = -1;
    for ( int i = 0 ;i < pArr.length;i++){
        pArr[i] = (pR > i) ? Math.min(pR - i ,pArr[ 2 * index - i]):1;
        while ( i + pArr[i] < pArr.length && i - pArr[i] >=0){
            if (chars[i + pArr[i]] == chars[ i - pArr[i]]){
                pArr[i]++;
            }else break;
        }
        if ( i + pArr[i] > pR){
            pR = i + pArr[i];
            index = i;
        }

        if (pR == chars.length){
            maxContainEnd = pArr[i];
            break;
        }
    }
    StringBuffer stringBuffer1 = new StringBuffer(revStr);
    for (int i = (pArr.length -(2 * maxContainEnd - 1)) /2 - 1; i >= 0;i--){
        stringBuffer1.append(stringBuffer1.charAt(i));
    }
    return String.valueOf(stringBuffer1);
}