5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.Scanner;

class Solution {

    private static char[] getManatcher(String s) {
        char[] ret = new char[s.length() * 2 + 1];
        for (int i = 0; i < s.length(); ++i) {
            ret[i * 2] = '#';
            ret[i * 2 + 1] = s.charAt(i);
        }

        ret[ret.length - 1] = '#';

        return ret;
    }

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

        char[] manatcher = getManatcher(s);

        int[] p = new int[manatcher.length];

        int c = -1, r = -1, max = -1, maxIndex = -1;

        for (int i = 0; i < manatcher.length; ++i) {
            p[i] = i > r ? 1 : Math.min(p[2 * c - i], r - i + 1);
            while (i + p[i] < manatcher.length && i - p[i] >= 0 && manatcher[i + p[i]] == manatcher[i - p[i]]) {
                p[i]++;
            }

            if (i + p[i] - 1 > r) {
                c = i;
                r = i + p[i] - 1;
            }

            // #0#
            // #0#1#
            // #0#1#2#
            if (p[i] > max) {
                max = p[i];
                maxIndex = i;
            }
        }

        /**
         * 关键点：从 # 映射到源字符串下表公式
         * (c - p + 1) / 2
         */
        int start = (maxIndex - max + 1) / 2;
        int end = (maxIndex + max - 1) / 2;

        return s.substring(start, end);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(longestPalindrome(in.next()));
        }
    }
}