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

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。