题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here

        // 填充字符串：123 -> #1#2#3#
        // 注意，两边也要有#，这样直接除以2就能返回结果，否则还要分类讨论
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A.length(); i++) {
            sb.append('#');
            sb.append(A.charAt(i));
        }
        sb.append('#');
        String newS = sb.toString();

        // 统计最长回文子串长度
        // 基础写法 - 空间复杂度O(1)，时间复杂度O(N2)；
        /*
        int max = 0;
        for (int i = 0; i < newS.length(); i++) {
            int l = i;
            int r = i;
            int len = 0;
            while (l >= 0 && r < newS.length() && newS.charAt(l) == newS.charAt(r)) {
                if (newS.charAt(l) != '#') {
                    if (l == r) {
                        len++;
                    } else if (l != r && newS.charAt(l) != '#') {
                        len += 2;
                    }
                }
                l--;
                r++;
            }
            if (len > max) {
                max = len;
            }
        }
        */

        // Manacher算法：空间复杂度O(N)，时间复杂度O(N)
        
        // 设置一个长度为n的数组：表示以当前元素为中心的回文半径；
        int[] lens = new int[newS.length()];
        // 设置两个全局的变量：当前最大回文字串的右边界与中心点
        // 初始化成-1，表示第一个元素就要外扩
        int c = -1;
        int b = -1;
        int max = 0;
        for (int i = 0; i < newS.length(); i++) {
            if (i > b) {
                // 1.当前元素超出了当前最大回文子串的右边界
                // 直接双指针暴力扩
                int left = i;
                int right = i;
                int len = 0;
                while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
                    if (left == right) {
                        len++;
                    } else if (left != right) {
                        len += 2;
                    }
                    left--;
                    right++;
                }
                if (len > max) {
                    // 若当前回文子串突破了最大值，则更新c和b
                    max = len;
                    c = i;
                    b = right - 1;
                }
                // 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
                lens[i] = right - 1 - i;
            } else {
                // 2.当前元素没有超过当前最大回文子串的右边界
                // 必然能找到i相对于c的对称元素iSym，观察iSym的回文子串情况，进行分类讨论
                int iSym = c * 2 - i;
                int iSymR = lens[iSym];
                int bSym = c * 2 - b;
                if ((iSym - iSymR) > bSym) {
                    // 2.1 iSym的回文区域完全包含在bSym...c...b内
                    // 说明i位置的元素回文子串必然没有突破b的限制，因此不必进行统计，直接沿用iSym的半径和直径，且不必更新c和b；
                    lens[i] = lens[iSym];
                } else if ((iSym - iSymR) < bSym) {
                    // 2.2 iSym的回文区域超出了bSym...c...b范围
                    // 说明iSym的回文超出bSym的部分必然没有对应在b处，要不然bSym和b的范围还会再此基础上再扩大，与当前确定的bSym和b范围相冲突，因此不必进行统计，i位置的回文半径就是i到b之间的部分，且不必更新c和b；
                    lens[i] = b - i;
                } else {
                    // 2.3 i’的回文区域正好达到了bSym之上：
                    // 说明i到b的部分必然是i位置元素的回文，这部分不必验证，直接验证外面的元素就好，再根据验证的情况决定是否更新c和b：
                    int right = b + 1;
                    int left = i * 2 - right;
                    int len = (b - i) * 2 + 1;
                    while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
                        if (left == right) {
                            len++;
                        } else if (left != right) {
                            len += 2;
                        }
                        left--;
                        right++;
                    }
                    if (len > max) {
                        // 若当前回文子串突破了最大值，则更新c和b
                        max = len;
                        c = i;
                        b = right - 1;
                    }
                    // 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
                    lens[i] = right - 1 - i;
                }
            }
        }
        // 记得除以2排除#字符
        return max / 2;
    }
}