《Manacher算法在计算最长回文子串长度中的应用.docx》由会员分享，可在线阅读，更多相关《Manacher算法在计算最长回文子串长度中的应用.docx（4页珍藏版）》请在三一文库上搜索。
1、Manacher算法在计算最长回文子串长度中的应用唐高阳【摘要】本文首介绍了如何运用Manacher算法在线性时间内找到一个字符串的最长回文子串。【关键词】Manacher算法；回文串；回文子串TheManacheralgorithmisusedtocalculatethelengthofthelongestreturnstringTANGGao-yangShenyanginstituteofscienceandtechnology，Shenyang，Liaoning110168【Abstract】Thispaperfirstintroducesamethodforfindingthelong
2、estpalindromesubsrtinginlineartimebytheManacherAlgorithm.【Keywords】Manacheralgorithm；Palindromesrting；Palindromesubsrting1遍历因为奇回文和偶回文在判断时比较麻烦，所以对str进行处理，把每个字符开头、结尾和中间插入一个特殊字符#来得到一个新的字符串数组。比方str=bcbaa，处理后为#b#c#b#a#a#，然后从每个字符左右扩出去的方式找最大回文子串就方便多了。对奇回文来说，不这么处理也能通过扩的方式找到，比方bcb，从c开始向左右两侧扩出去能找到最大回文。处理后为#b#
3、c#b#，从c开始向左右两侧扩出去依然能找到最大回文。对偶回文来说，不处理而直接通过扩的方式是找不到的，比方aa，因为没有确定的轴，但是处理后为#a#a#，就可以通过从中间的#扩出去的方式找到最大回文。所以通过这样的处理方式，最大回文子串无论是偶回文还是奇回文，都可以通过统一的“扩过程找到，解决了差异性的问题。同时要说的是，这个特殊字符是什么无所谓，甚至可以是字符串中出现的字符，也不会影响最终的结果，就是一个纯辅助的作用。具体的处理过程请参看如下代码中的manacherString方法。publiccharmanacherStringStringstrcharcharArr=str.toCha
4、rArray；charres=newcharstr.length*2+1；intindex=0；fori=0；I！=res.length；i+resi=i&1=0？#：charArrindex+；Returnres；2优化假设str处理之后的字符串记为charArr。对每个字符包括特殊字符都进行“优化后的扩过程。3扩过程只要能够从左到右依次算出数组pArr每个位置的值，最大的那个值实际上就是处理后的charArr中最大的回文半径，根据最大的回文半径，再对应回原字符串的话，整个问题就解决了。步骤3就是从左到右依次计算出pArr数组每个位置的值的过程。1假设现在计算到位置i的字符charA
5、rri，在i之前位置的计算过程中，都会不断地更新pR和index的值，即位置i之前的index这个回文中心扩出了一个目前最右的回文边界pR。2如果pR-1位置没有包住当前的i位置。比方“#c#a#b#a#c#，计算到charArr【1】=c时，pR为1。也就是说，右边界在1位置，1位置为最右回文半径即将到达但还没有到达的位置，所以当前的pR-1位置没有包住当前的i位置。此时和普通做法一样，从i位置字符开始，向左右两侧扩出去检查，此时的“扩过程没有获得加速。3如果pR-1位置包住当前的i位置。比方“#c#a#b#a#c#，计算到charArr610时，pR都为11，此时pR-1包住了位置6-10
6、。这种情况下，检查过程是可以获得优化的，这也是manacher算法的核心内容。4进阶问题按照步骤3的逻辑从左到右计算出pArr数组，计算完成后再遍历一遍pArr数组，找出最大的回文半径，假设位置i的回文半径最大，即pArri=max。但max只是charArr的最大回文半径，还得对应回原来的字符串，求出最大回文半径的长度其实就是max-1。在charArr中位置3的回文半径最大，最大值为4即pArr【3】=4，对应原字符串的最大回文子串长度为4-1=3。Manacher算法时间复杂度是ON的证明。虽然我们可以很明显地看到Manacher算法与普通方法相比，在扩出去检查这一行为上有明显的优化，但
7、如何证明该算法的时间复杂度就是ON呢？关键之处在于估算扩出去检查这一行为发生的数量。原字符串在处理后的长度由N变为2N，从步骤3的主要逻辑来看，要么在计算一个位置的回文半径时完全不需要扩出去检查，比方，步骤3的中3介绍的情况一和情况二，都可以直接获得位置i的回文半径长度；要么每一次扩出去检查都会让回文半径到达更右的位置，当然会使pR更新。然而pR最多是从-1增加到2N右边界，并且从来不减小，所以扩出去检查的次数就是ON的级别。所以Manacher算法時间复杂度是ON。具体请参看如下代码中的maxLcpsLength方法。publicstaticintmaxLcpsLengthStringstr
8、ifstr=null|str.length=0endprintreturn0；charcharArr=manacherStringstr；intpArr=newintcharArr.length；intindex=-1；intpR=-1；intmax=Integer.MIN_VALUE；forinti=0；i！=charArr.length；i+pArri=pR>i？Math.minpArr2*index-i，pR-i：1；whilei+pArri-1ifcharArri+pArri=charArri-pArripArri+；elsebreak；ifi+pArri>pRpR=i+p
9、Arri；index=i；max=Math.maxmax，pArri；returnmax-1；在字符串的最后添加最少字符，使整个字符串都成为回文串，其实就是查找在必须包含最后一个字符的情况下，最长的回文串是什么之前不是最长回文子串的局部逆序过来，就是应该添加的局部。比方“abcd123321，在必须包含最后一个字符的情况下，最长的回文子串是“123321，之前不是最长回文子串的局部是“abcd，所以末尾应该添加的局部就是“dcba只要把manacher算法稍作修改就可以。具体改为：从左到右计算回文半径时，关注回文半径最右即将到达的位置pR，一旦发现已经到达最后pR=charArr.length
10、，说明必须包含最后一个字符的最长回文半径已经找到，直接退出检查过程，返回该添加的字符串即可。具体过程参看如下代码中的shortestEnd方法。publicstaticStringshortestEndStringstrifstr=null|str.length=0returnnull；charcharArr=manacherStringstr；intpArr=newintcharArr.length；intindex=-1；intpR=-1；intmaxContainsEnd=-1；forinti=0；i！=charArr.length；i+pArri=pR>i？Math.minpAr
11、r2*index-i，pR-i：1；whilei+pArri-1ifcharArri+pArri=charArri-pArripArri+；elsebreak；ifi+pArri>pRpR=i+pArri；index=i；ifpR=charArr.lengthmaxContainsEnd=pArri；break；charres=newcharstr.length-maxContainsEnd+1；forinti=0；iresres.length-1-i=charArri*2+1；returnString.valueOfres；5結果与分析Manacher算法是由GlennManacher
12、于1975年首次创造的，比起能够解决该问题的其他算法，Manacher算法算比较好理解和实现的。【参考文献】【1】BruceEckel.?Java编程思想?.机械工业出版社.2021.6.1.【2】梁勇.?Java语言程序设计根底篇?.机械工业出版社2021.7.1.【3】梁勇.?Java语言程序设计进阶篇?.机械工业出版社.2021.10.1.【4】ThomasH.Cormen；CharlesE.Leiserson；RonaldL.Rivest；CliffordStein?算法导论?机械工业出版社.2021.7.1.【5】MarkAllenWeiss.?数据结构与算法分析Java语言描述?.机械工业出版社.2021.1.1.【6】RobertSedgewick.KevinWayne.?算法第4版?人民邮电出版社.2021.10.1.endprint