题解 | #编号子回文I#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String longestPalindrome (String s) {
        int n = s.length() ; 
        char[] chs = new char[n*2+1] ;
        chs[0] = '#' ; 
        for(int i = 0;i < s.length();i++){
            chs[2*i+1] = s.charAt(i) ; 
            chs[2*i+2] = '#' ; 
        }
        int c = 0 ;
        int len = 0 ; 
        int ans = 0 ; 
        int cc = 0 ; 
        int[] nums = new int[chs.length] ; 
        for(int i = 0;i < chs.length;i++){
            int pi = 2*c-i ; 
            if(pi >= 0 && nums[pi] < len+c-i){
                nums[i] = nums[pi] ; 
            }else{
                int j =  pi >= 0 ? nums[pi] : 0 ; 
                while(i - j >= 0 && i + j < chs.length){
                    if(chs[i-j] != chs[i+j]){
                        break ; 
                    }
                    j++ ; 
                }
                nums[i] = j; 
                if(i + j > c+len){
                    c = i ; 
                    len = j ; 
                }
                if(j > ans){
                    ans = j ; 
                    cc = i ; 
                }
            }
        }
        StringBuilder sb = new StringBuilder("") ; 
        for(int i = cc-ans+1;i <= cc+ans-1;i++){
            if(chs[i] == '#'){
                continue ; 
            }
            sb.append(chs[i]) ; 
        }
        return sb.toString(); 
        // write code here
    }
}

马拉车算法 O(n)复杂度