Manacher 入门+模板 回文串专用算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Manacher 入门+模板 回文串专用算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含734字，纯文字阅读大概需要2分钟。

内容图文

Manacher 算法 回文串专用算法

manacher 人名，该算法的发明者。palindrome名词：回文。

博客推荐

https://www.cnblogs.com/lykkk/p/10460087.html，比较简洁，代码清晰。

https://www.cnblogs.com/cloudplankroader/p/10988844.html， 一些细节的东西比较讲解比较细。

模板

//预处理函数，使得处理后的字符串长度为奇数，并且有一些比较好的性质
int init(char* s, char* ss)
{
    int len=strlen(s);
    ss[0]='@'; ss[1]='#';
    int j=2;
    for(int i=0; i<len; i++)
    {
        ss[j++]=s[i];
        ss[j++]='#';    
    }
    ss[j]='\0';
    return j;   
}

//时间复杂度为O(N)
int manacher(char *st, int len)
{
    int mx=0, ans=0, po=0;
    for(int i=1; i<=len; i++)
    {
        if(mx>i)
            p[i]=min(mx-i, p[2*po-i]);
        else 
            p[i]=1;
        while( st[i-p[i] ] == st[ i+p[i] ] ) p[i]++;
        if(p[i]+i > mx)
        {
            mx=p[i]+i;
            po=i;
        }
        ans=max(ans, p[i]);
    }
    return ans-1;
}

内容总结

以上是互联网集市为您收集整理的Manacher 入门+模板 回文串专用算法全部内容，希望文章能够帮你解决Manacher 入门+模板 回文串专用算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---