Manacher算法要会，O(n)的算法，根据回文串的子串特征减少不必要的比较和搜索，字符串这里的算法提出者真的让人佩服

class Solution {
public:
    string init(string A){
        string newA = "#";
        for(int i = 0; i < A.size(); i++){
            newA += A[i];
            newA += "#";
        }
        return newA;
    }
    int getLongestPalindrome(string A, int n) {
        // write code here
        string newA = init(A);
        int* p = new int[newA.size()];
        for(int i = 0 ; i < newA.size(); i++)
            p[i] = 1;
        p[0] = 1;
        int i = 1;
        while(i < newA.size()){
            int lo = i - p[i];
            int hi = i + p[i];
            while(lo >= 0 and hi < newA.size())
                if(newA[lo] == newA[hi]){
                    p[i]++;
                    lo--;
                    hi++;
                }else
                    break;
            
            int j = 1;
            for(j = 1; j < p[i] ; j++){
                int newi = j + i;
                if(newi >= newA.size())
                    break;
                int newi_symmetry = 2 * i - newi;
                // newi_symmetry一定在newA范围内
                if(newi_symmetry - p[newi_symmetry] == i - p[i] ){
                    // newi处于不可判断的状态
                    p[newi] = p[newi_symmetry];
                    
                    break;
                }
                else{
                    p[newi] = min(p[newi_symmetry], newi_symmetry - i + p[i]);
                }
            }
            i = j + i;
        }
        int ma = -1;
        for(i = 0 ; i < newA.size() ; i++){
            if(ma < p[i] - 1)
                ma = p[i] - 1;
        }
        return ma;
        
    }
};