题解 | #最长回文子串#

   /**
     * ☆☆☆☆☆
     * 最长回文子串
     * 中心扩展 + 动态规划 + Manacher
     */
    private static void longestPalindrome() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            // 字符间隔及两边插入#，方便统一中心扩展方式的两种情况：中心在元素上和中心在元素间
            StringBuilder sb = new StringBuilder("#");
            for (int i = 0; i < s.length(); i++) {
                sb.append(s.charAt(i)).append("#");
            }
            // 数组用于存插入#后，当前元素为中心的最大回文半径（自身算1）
            // 最终的最大回文长度是该半径-1（该半径多出来的#，比另一边的原字符多一）
            int[] arr = new int[sb.length()];
            // 已知的所有回文串的最右边界+1
            int maxPos = 0;
            // 边界最右的回文串的中心
            int index = 0;
            for (int i = 0; i < sb.length(); i++) {
                if (i < maxPos) {
                    // 此处是关键，i相对index的对称位置2*index-i，直接参与计算，避免重复计算
                    arr[i] = Math.min(arr[2 * index - i], maxPos - i);
                } else {
                    arr[i] = 1;
                }
                // 在已有基础上继续扩展判断，越界判断，以及两边字符判断
                while (i - arr[i] >= 0 && i + arr[i] < sb.length() && sb.charAt(i - arr[i]) == sb.charAt(i + arr[i])) {
                    arr[i]++;
                }
                // 更新maxpos和index
                if (i + arr[i] > maxPos) {
                    maxPos = i + arr[i];
                    index = i;
                }
            }
            int max = 0;
            for (int i = 0; i < sb.length(); i++) {
                max = Math.max(max, arr[i]);
            }
            // 最长回文串的长度
            System.out.println(max - 1);
            // 最长回文串
            for (int i = 0; i < sb.length(); i++) {
                if (max == arr[i]) {
                    String result = sb.substring(i - arr[i] + 1, i + arr[i]).replace("#", "");
                    System.out.println(result);
                    break;
                }
            }
        }
    }