这是一道回文串的模板题，我们只要记录回文串的半径和开始的位置就能AC。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String tempStr = "#";
        for(int i = 0; i < n; i++){
            tempStr += s.charAt(i)+"#";
        }
        int MX = 0, pos = 0, ans = 0, P[] = new int[2*n +1], reIndex = 0;
        for(int i = 0; i < tempStr.length(); i++){
            if(i >= MX){
                P[i] = 1;
            }else{
                P[i] = Math.min(P[2*pos-i], MX-i);
            }
            while((i - P[i] >= 0 && i+P[i] < tempStr.length()) &&tempStr.charAt(i+P[i])== tempStr.charAt(i-P[i])){
                P[i]++;
            }
            if(P[i] > ans){
                ans = P[i];
                reIndex = i;
            }
            if(MX < P[i] + i){
                MX = P[i] + i;
                pos = i;
            }
	}
        return s.substring((reIndex- ans +1)/2, (reIndex+ans)/2);
    }
}