题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）

解法1：马拉车算法
加工字符串
利用中心位C拓展找到基线P[i]
在基线上继续中心扩张回文子串长度P[i]
修改中心位置C，改变边界R

class Solution {
    public String preProcess(String s){
            int n = s.length();
            if(n==0){
                return "^$";
            }
            String ret="^";
            for(int i =0 ; i<n;i++){
                ret+="#"+s.charAt(i);
            }
            return ret += "#$";
        }
    public String longestPalindrome(String s) {
        String T =preProcess(s);
        int n =T.length();
        int[] P=new int[n];
        int C=0,R=0;
        //从1个开始，到n-1个结束，是为了防止越界
        for(int i =1 ; i<n-1;i++){
            //寻找P[i]的基线
            int i_mirror=2*C-i;
            if(R>i){
                //在边界里面
                P[i]=Math.min(P[i_mirror], R-i);
            }else{
                P[i]=0;
            }
            //基线+不断摸索扩展=真实P[i]
            while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i])){
                P[i]++;
            }
            //如果真实P[i]越过了边界的话
            if(i+P[i]>R){
                C=i;//更改中心位置
                R=i+P[i];//更改边界位置
            }
        }
        //寻找P[x]最大值
        int len=0;
        int index=0;
        for(int i =1;i<n-1;i++){
            if(P[i]>len){
                len=P[i];
                index=i;
            }
        }
        int start=(index-len)/2;//寻找最初位置
        return s.substring(start,start+len);
        
    }
}