有哪些信誉好的足球投注网站- 1、本文档共9页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
Manacher算法
主讲人：邓哲也
回文串
对于一个长度为n的字符串str，如果它正着读和反着读
一样，即str[i]=str[n-i+1](1=in-i+1)
如aba，acbbca就是回文串，abc，abab就不是回文串。
Manacher算法
Manacher算法可以求出以每个位置为中心，向两边能扩展
的最长回文子串长度p[i]，它的时间复杂度是O(n)的。
注意到回文子串的长度可能是偶数，如abba，中心不是某
个字符（中心是两个b之间的空隙），所以先要在相邻的
字符中插入一个标识符，例如#
这样例如#a#b#b#a#的中心就是#了。
Manacher算法
我们用abbabcba来举例。
先插入#得到#a#b#b#a#b#c#b#a#。
然后用Manacher可以得到如下的p数组。
对于每个p[i]，一定有str[i+j]==str[i-j](1≤jp[i])
str#a#b#b#a#b#c#b#a#
p[i]12125214121612121
Manacher算法
类比Z算法，我们也维护一个mx和id，表示对于当前计
算的所有i，i+p[i]的最大值是mx，mx对应的i记为
id。
当你现在开始计算p[i]时，默认p[1..i-1]都已经算出。
如果mxi，那么p[i]=min(p[2*id-i],mx-i)
Manacher算法
当mx-ip[j],那么p[i]=p[j]
否则p[i]=mx-i,且需要进一步判断
Manacher算法代码实现
intid,mx=0;
for(inti=1;in;i++){
if(mxi)p[i]=min(p[2*id-i],mx-i);
elsep[i]=1;
while(str[i+p[i]]==str[i-p[i]])p[i]++;
if(i+p[i]mx)mx=i+p[i],id=i;
}
Manacher算法
Manacher算法的时间复杂度是O(n)的。
考虑mx的移动。
mx最多从0移到n。
而一次字符串比较会让mx右移一次。
因此最多只会比较n次字符相等。
时间复杂度O(n)
下节课再见
文档评论（0）