NC17 最长回文子串

描述
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

思路：以某个字符为中心，向左右两边扩展。
1）需要考虑当我们在寻找的回文为奇或偶时的情况 O(N^2)
2）不想考虑奇偶情况，可以给字符串预处理，每个字符左右加上特殊字符‘#’（任意字符都可）,O(N^2)
3）manacher 算法 O(N)
视频地址 https://www.bilibili.com/video/BV13g41157hK?p=13
文章讲解： https://www.jianshu.com/p/116aa58b7d81

package mid;

public class MaxHuiWenSubStr {
    public static void main(String[] args) {
        String str = "abc11cba";
        int ans = manacher(str);
        System.out.println(ans);
        int ans1 = maxHuiWenLength(str);
        System.out.println(ans1);
        int ans2 = maxHuiWenLength2(str);
        System.out.println(ans2);
        int ans3 = maxHuiWenLength3(str);
        System.out.println(ans3);
    }

    //将字符串添加特殊符号
    public static char[] changeString(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 O(N)
    public static int manacher(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        //将字符串添加特殊符号
        char[] charArr = changeString(str);
        //回文半径数组
        int[] pArr = new int[charArr.length];
        int C = -1;//回文的中心
        int R = -1;//回文的最右位置
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < charArr.length; i++) {
            pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - 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] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;

    }


//不考虑奇偶，直接给原数组加'#'的写法 O(N^2)
    public static int maxHuiWenLength1(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        //将字符串添加特殊符号
        char[] charArr = changeString(str);

        int max = Integer.MIN_VALUE;
        //以i为中心，向最右两边扩展
        for (int i = 0; i < charArr.length; i++) {
            int l=i-1,r=i+1;
            int tempMax=1;
            while (l>-1 && r<charArr.length){
                if (charArr[l]!=charArr[r]){
                    break;
                }
                l--;
                r++;
                tempMax+=2;
            }
            max=Math.max(tempMax,max);
        }
        return max>>1;
    }


    //回文奇偶分类 ,写入同一个for O(N^2)
    public static int maxHuiWenLength2(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        char[] charArr = str.toCharArray();
        //以i为中心，向最右两边扩展
        for (int i = 0; i < charArr.length; i++) {
            //奇数
            int l=i-1,r=i+1;
            int tempMax=1;
            while (l>-1 && r<charArr.length){
                if (charArr[l]!=charArr[r]){
                    break;
                }
                l--;
                r++;
                tempMax+=2;
            }
            max=Math.max(tempMax,max);

            //偶数
            int l2=i,r2=i+1;
            int tempMax2=0;
            while (l2>-1 && r2<charArr.length){
                if (charArr[l2]!=charArr[r2]){
                    break;
                }
                l2--;
                r2++;
                tempMax2+=2;
            }
            max=Math.max(tempMax2,max);
        }
        return max;

    }


    //回文奇偶分类 O(N^2)
    public static int maxHuiWenLength3(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        char[] charArr = str.toCharArray();
        //以i为中心，向最右两边扩展
        for (int i = 0; i < charArr.length; i++) {
            //当回文为奇数时
            int l=i-1,r=i+1;
            int tempMax=1;
            while (l>-1 && r<charArr.length){
                if (charArr[l]!=charArr[r]){
                    break;
                }
                l--;
                r++;
                tempMax+=2;
            }
            max=Math.max(tempMax,max);
        }
        //当回文为偶数时
        for (int i = 0; i < charArr.length; i++) {
            int l=i,r=i+1;
            int tempMax=0;
            while (l>-1 && r<charArr.length){
                if (charArr[l]!=charArr[r]){
                    break;
                }
                l--;
                r++;
                tempMax+=2;
            }
            max=Math.max(tempMax,max);
        }
        return max;

    }
}