5. Longest Palindromic Substring

package com.chanmufeng.leetcode;

/**
 * faster than 61.63%
 * 最后求取子串的处理不是很地道
 */
public class LongestPalindromicSubString_5 {
    private static char[] manacherString(String str) {
        char[] strArr = new char[str.length() * 2 + 1];
        int index = 0;
        strArr[index++] = '#';
        for (int i = 0; i < str.length(); i++) {
            strArr[index++] = str.charAt(i);
            strArr[index++] = '#';
        }
        return strArr;
    }


    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return "";

        char[] strArr = manacherString(s);
        int[] pArr = new int[strArr.length];
        int C = -1;
        int R = -1;
        int pivotIndex = 0;
        int maxLength = Integer.MIN_VALUE;
        for (int i = 0; i < strArr.length; i++) {
            pArr[i] = R > i ? Math.min(R - i, pArr[2 * C - i]) : 1;
            while (i - pArr[i] > -1 && i + pArr[i] < strArr.length) {
                if (strArr[i + pArr[i]] == strArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            if (maxLength < pArr[i]) {
                maxLength = pArr[i];
                pivotIndex = C;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = pivotIndex - maxLength + 1; i <= pivotIndex + maxLength - 1; i++) {
            if (strArr[i] != '#') {
                sb.append(strArr[i]);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String test = "babad";//3 3
        String test1 = "cbbd";//4 2

//        int[] res = manacher(test);
//        System.out.println(res[0] + " " + res[1]);
//        System.out.println(manacher("cbbd"));
    }
}