mannachar(马拉车)求最长回文子串

mannachar(马拉车)究竟是什么东西呢？
很简单，就是能让你在O（n）的复杂度内求出一个串的最长回文子串。传统的算法复杂度是O（n^2），呐，为什么mannachar能变快呢？因为mannachar用到了算过的东西来进行优化。脑补一下，当你发现了一个回文串，那么是不是左右就对称了呢？然后左边的最长回文子串是已经求过了，所以右边对应的点的最长回文子串至少也有那么多。
先贴一波代码

#include
#include
template <typename T>inline T max(const T x,const T y){return x>y?x:y;}
template <typename T>inline T min(const T x,const T y){return xchar s[11000001],t[22000010];
int p[22000002],len,l;
int main()
{scanf("%s",s+1),len=strlen(s+1);t[l++]='$',t[l++]='#';for(register int i=1;i<=len;i++)t[l++]=s[i],t[l++]='#';int maxx=0,num=0,res=0;for(register int i=0;ii?min(p[(num<<1)-i],maxx-i):1;while(t[i+p[i]]==t[i-p[i]])p[i]++;if(i+p[i]>maxx){maxx=i+p[i];num=i;}res=max(res,p[i]);}printf("%d",res-1); return 0;
}

它的复杂度是O（n）的，为什么呢？请看我的代码中的maxx这个变量表示现在最长回文子串的右边界的最远值，最多移动n次，复杂度就证好啦
其实mannachar并不难，不过说实话用的场合不是很多，所以嘛，学一下，掌握一下就好啦，再去学字符串的其它算法组合一下就能做出一些题啦

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！