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;  
      
    }