manacher算法的實現

    //求字符串s中最大回文的長度,要求字符串s不包含字符‘#’

    int manacher(const string &s)

    {

        if (s.size() <= 1)

            return s.size();


    //往s每個字符之間以及s的首尾都插入‘#’  
    string str(s.size() * 2 + 1, '#');  
    for (int i = 0, j = 1; i<s.size(); ++i, j += 2)  
        str[j] = s[i];  

    int maxr = 2, id = 1, size = str.size();//maxr是當前最大回文的半徑  
    vector<int> p(size, 1);  
    p[1] = 2;  

    for (int i = 2; i <= size-3; ++i)  
    {  
        int maxright = p[id] + id - 1;  
        if (i>maxright)  
        {  
            while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])  
                ++p[i];  
        }  
        else  
        {  
            int idleft = id - p[id] + 1;  
            int k = i - id, j = id - k, tmp = j - p[j] + 1;//i和j關于id對稱  
            if (tmp>idleft)  
                p[i] = p[j];  
            else if (tmp<idleft)  
                p[i] = p[id] - k;  
            else  
            {  
                p[i] = p[j];  
                while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])  
                    ++p[i];  
            }  

        }  
        if (p[i] + i>p[id] + id)  
            id = i;  
        maxr = max(maxr, p[i]);  
    }  

    return maxr - 1;  

}  </pre>