江苏龙网

  1. 首页 > 资讯 > 科技 > >

『IT知识课堂TB』求最长回文子串算法——马拉车算法


Manacher's Algorithm ， 中文名叫马拉车算法 ， 是一位名叫Manacher的人在1975年提出的一种算法 ， 解决的问题是求最长回文子串 ， 神奇之处在于将算法的时间复杂度精进到了O(N) ， 下面我们来详细介绍下这个算法的思路 。
01 算法由来
在求解最长回文子串的问题时 ， 一般的思路是以当前字符为中心 ， 向其左右两边扩展寻找回文 ， 但是这种解法的时间复杂度是O(N^2) ， 那么能不能将时间复杂度再降低一点？做到线性？马拉车算法就完美地解决了这个问题 。
02 预处理
回文字符串以其长度来分 ， 可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数） ， 一般情况下需要分两种情况来寻找回文 ， 马拉车算法为了简化这一步 ， 对原始字符串进行了处理 ， 在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符） ， 让字符串变成一个奇回文 。 例如：
原字符串：abba ， 长度为4 预处理后：#a#b#b#a# ， 长度为9
原字符串：aba ， 长度为3 预处理后：#a#b#a# ， 长度为7
03 计算最长回文子串长度
以字符串"cabbaf"为例 ， 将预处理后的新字符串"#c#a#b#b#a#f#"变成一个字符数组arr ， 定义一个辅助数组int[] p ， p的长度与arr等长 ， p[i]表示以arr[i]字符为中心的最长回文半径 ， p[i]=1表示只有arr[i]字符本身是回文子串 。
i 0 1 2 3 4 5 6 7 8 9 10 11 12
arr[i] # c # a # b # b # a # f #
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
我们来比对分下一下最长回文半径和原字符串之间的关系 。 在上面例子中 ， 最长回文子串是"#a#b#b#a#" ， 它以arr[6]为中心 ， 半径是5 ， 其代表的原始字符串是"abba" ， 而"abba"的长度为4 ， 可以通过5减去1得到 ， 是字符串"cabbaf"中的最长回文子串 ， 那么我们是不是可以得出最长回文半径和最长回文子串长度之间的关系？
让我们再多看几个例子 ， 如"aba" ， 转换后是"#a#b#a#" ， 以字符'b'为中心的回文 ， 半径是4 ， 减1得到3 ， 3是原字符串的最长回文子串长度 。
再例如"effe" ， 转换后是"#e#f#f#e#" ， 以最中间的'#'为中心的回文 ， 半径是5 ， 减1得到4 ， 4是原字符串的最长回文子串长度 。
因此 ， 最后我们得到最长回文半径和最长回文子串长度之间的关系：int maxLength = p[i]-1 。 maxLength表示最长回文子串长度 。
04 计算最长回文子串起始索引
知道了最长回文子串的长度 ， 我们还需要知道它的起始索引值 ， 这样才能截取出完整的最长回文子串 。
继续以第三步中的字符串"cabbaf"为例 ， p[6]=5 ， 是最长半径 ， 用6(i)减去最长半径5(p[i])得到1 ， 而1恰好是最长回文子串"abba"的起始索引 。
我们再来看一个奇回文的例子 。 例如"aba" ， 转换后是"#a#b#a#" ， p[3]=4 ， 最长半径是4 ， i为3 ， 用i减去4得到-1 ， 数组下标越界了 。
在偶回文的情况下 ， 可以满足i减最长半径 ， 而奇回文却会下标越界 ， 我们需要在转换后的字符串前面再加一个字符 ， 解决下标越界的问题 ， 不能是'#' ， 那就加个'$'字符吧 ， 但是加过一个字符后 ， 字符串的长度不是奇数了 ， 只能在尾部再加一个不会重复出现的字符 ， 比如'@' ， 这样字符串的长度依旧是奇数了 ， 满足前面第三部分的条件 。
加多一个字符后 ， 奇回文可以正常做减法了 ， 偶回文呢？
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13
arr[i] $ # c # a # b # b # a # f #
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
在补上字符'$'后 ， p[7]=5 ， 用i减去最长半径 ， 7-5=2 ， 而理想的结果应该是1 ， 那就再除以2吧 ， 这样就能得到1了 。 而奇回文"aba"在用i减去最长半径后得到的是0 ， 除以2后还是0 ， 可以完美解决下标越界的问题 。


推荐阅读


上一篇：【长旭数码】华为新机发布不断，荣耀30将搭载麒麟985处理器，颜值担当

下一篇：[蓝牙]基于BlueCore2External芯片的蓝牙主机模型方案