锐客网

  1. 首页 > it技术 > >

Manacher算法「最长回文字符串」

算法原理
  • 最长回文字符串包括奇数长的和偶数长的，求的时候都要分情讨论,Manacher算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘#’字符。
    这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心奇数回文串了。
    其次给每个字符串首部加一个题目中不会出现的字符，避免处理越界问题。（一般加’$’）

    Manacher算法「最长回文字符串」
    文章图片

    如图字符串就是通过算法预处理得到的新串
    数组记录的以 为中间字符的回文串向右能匹配的最大长度(包括S[i]这个字符).
    当不是所加字符‘#’时，就是字符串长度了【Manacher算法「最长回文字符串」】
  • 假设以i为中心的回文串长度为,因为]记录以 为中间字符的回文串向右能匹配的长度，所以有

    又因为此时串中加了其他字符#，以为中心的回文串一定是以#开头和结尾的，以#为中间字符的就是长度为偶数的，以非#号为中间字符的就是长度为奇数的，例如“#b#b#”或“#b#a#b#”所以减去最前或者最后的‘#’字符就是原串中长度的2倍，即原串长度为，化简的。
算法实现
  • 算法实现就是要找出数组,如何找出数组是关键.
首先从左往右依次计算，当计算时，已经计算完毕。设为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为，分两种情况：
情况1：

  1. 那么找到相对于的对称位置，设为，那么如果
    因为,能向左匹配的最左端点的坐标是
    所以可知,所以可知
    向如下图：
    Manacher算法「最长回文字符串」
    文章图片

    那么说明以为中心的回文串一定在以为中心的回文串的内部，且和关于位置对称,那么意味着以为中间字符的回文串能向右匹配最右端点没有超过。由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，所以。
  2. 如果,由对称性，说明以为中心的回文串可能会延伸到之外，而大于的部分我们还没有进行匹配，所以要从位置开始一个一个进行匹配，直到发生失配，从而更新和对应的以及。
    Manacher算法「最长回文字符串」
    文章图片

    虽然p[j]>mx-i,但是可以保证的是这一段是跟是一样的，说明以s[i]为中心的回文串至少有这么长
情况2：

如果i比mx还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新的位置和对应的以及。

Manacher算法「最长回文字符串」
文章图片

int len=strlen(s); int mx=0; int id=0; int res=-1; for(int i=len; i>=0; i--) { s[i*2+2]=s[i]; s[i*2+1]='#'; } s[0]='$'; //加上特殊字符防止越界 for(int i=0; i<=2*len+1; i++) { if(mx>i)//mx=mx，要从头开始匹配 { p[i]=1; } while(s[i-p[i]]==s[i+p[i]])//一个一个比较 { p[i]++; } if(p[i]+i>mx))//若新计算的回文串右端点位置大于mx，要更新id和mx的值{ mx=p[i]+i; id=i; } res=max(res,p[i]-1); }

    推荐阅读


    上一篇：孟小冬与梅兰芳:曾经你也是我的一切

    下一篇：1231|1231|7天阅读变现营D4