网站备案详细流程,重庆网站建设及推广公司,游戏网站做的思想步骤,网站建设的语言写在前面 manachermanachermanacher比想象中好理解得多
至少它给了我学习字符串的信心
能干啥 manachermanachermanacher#xff0c;中文马拉车#xff08;您别说#xff0c;这名字还挺形象#xff09;#xff0c;主要用于计算字符串每一个位置为对称中心的回文串长度中文马拉车您别说这名字还挺形象主要用于计算字符串每一个位置为对称中心的回文串长度等价于个数
包括偶回文即长度为偶数的回文串
算法流程
考虑下面的问题给一个字符串求最长回文子串
我会暴力
枚举判断O(n3)O(n^3)O(n3)
我会优化
考虑到以ccc为中心acbacbacb不是回文串左右怎么接都不是回文串
所以可以枚举中间点偶回文判断一下即可然后向两边拓展
复杂度O(n2)O(n^2)O(n2)
我会玄学
O(n2)O(n^2)O(n2)还不够 不符合字符串算法均为线性复杂度公理
在此基础上继续优化
我们记录maxrmaxrmaxr为目前找到的回文串右端点的最右的位置 pospospos为这个回文串的对称中心
开一个数组pip_ipi表示回文半径和其他文章不同本文回文半径指一个端点到中心的距离即直接相减
回文串最本质的特征是什么左右关于中心对称。
如果一个回文串对称中心的一侧有另一个回文子串那么对称过去也有一个相同长度的回文子串 黄色部分完全一致这就是manacher的核心
先不考虑偶回文
① ilt;maxrilt;maxrimaxr(取不取等于无所谓)
设j,ij,ij,i关于pospospos对称 即jpos∗2−ijpos*2-ijpos∗2−i
根据上面的推导令pipjp_ip_jpipj即可
当然如果jjj为中心的最长回文左端点越界了 那就不能保证上面的性质实际上可以保证不成立所以要和j−maxlj-maxlj−maxl(即maxr−imaxr-imaxr−i)取minminmin。
jjj越界时还需要让iii继续拓展。当然为了刷短代码减少讨论都拓展一下好了
②i≥maxri \geq maxri≥maxr 啥都不能保证直接暴力扩展
综上
如果ilt;maxrilt;maxrimaxr,按上述条件更新pip_ipi暴力拓展更新maxrmaxrmaxr和pospospos
然后……对没了就三行。
这就是manachermanachermanacher的全过程复杂度O(n)O(n)O(n)后面有证明
实现
上面没有讨论偶回文主要是转化过程比较难看容易使人丧失信心。
其实也不难。只需要在字符两两之间加一个字符,如‘#’然后首尾也加上‘#’再在开头加一个标识符防止越界。注意要和之前的不同如‘’
这样偶回文可以看做中心是‘#’的回文
普及T1模拟水平
这样处理后所有回文串左右端点都是‘#’然后就可以跑了
证明
什么不是只改了一个地方吗怎么变O(n)O(n)O(n)了
回顾整个流程真正暴力拓展的时候要么jjj左端点越界要么iii越界(jjj左端点没越界时根据反证法iii实际上无法拓展)
jjj左端点越界时iii右端点出生点就在maxrmaxrmaxr再拓展就超出去了
也就是说每次暴力拓展都意味着maxrmaxrmaxr更新而maxrmaxrmaxr只会往右跑
换一个角度实际上暴力拓展是把maxrmaxrmaxr推到最右边次数是O(n)O(n)O(n)的
所以总复杂度是O(n)O(n)O(n)的
代码
#include iostream
#include cstdio
#include cstring
#define MAXN 1000005
using namespace std;
char s[MAXN],ss[MAXN];
int pos,maxr;
int p[MAXN];
int main()
{scanf(%s,s1);int nstrlen(s1);for (int i1;in;i) ss[i1]s[i],ss[(i1)|1]#;n(n1)|1,ss[0],ss[1]#;strcpy(s,ss);for (int i1;in;i){if (imaxr) p[i]min(p[(pos1)-i],maxr-i);while (s[i-p[i]-1]s[ip[i]1]) p[i];if (ip[i]maxr) maxrip[i],posi;}return 0;
}由于所有位置为中心的最长回文串左右端点都是‘#’
回文串长度leni2pi1−12pilen_i \frac {2p_i1-1}{2} p_ileni22pi1−1pi
然后用来搞事情就可以了
