【相当困难】Manacher算法－Java：原问题

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; /** * Manacher算法 * * 【题目】 * 给定一个字符串str，返回str中最长回文子串的长度。 * * 【举例】 * str="123"，其中的最长回文子串为"1"、"2"或者"3"，所以返回1。 * str="abc1234321ab"，其中的最长回文子串为"1234321"，所以返回7。 * * 【进阶题目】 * 给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添 * 加的最短字符串。 * * 【举例】 * str="12"。在末尾添加"1"之后，str变为"121"，是回文串。在末尾添加"21"之后，str变为"1221"，也是回文串。但"1"是所有 * 添加方案中最短的，所以返回"1"。 * * 【要求】 * 如果str的长度为N，解决原问题和进阶问题的时间复杂度都达到O(N)。 * * 【难度】 * 相当困难 * * 【解答】 * 本文的重点是介绍Manacher算法，该算法是由Glenn Manacher于1975年首次发明。Manacher算法解決的问题是在线性时间内找 * 到一个字符串的最长回文子串，比起能够解决该问题的其他算法，Manacher算法算比较好理解和实现的。 * * 先来说一个很好理解的方法。从左到右遍历字符串，遍历到每个字符的时候，都看看以这个字符作为中心能够产生多大的回文字符串。 * 比如str="abacaba"，以str[0]=='a'为中心的回文字符串最大长度为1，以str[1]=='b'为中心的回文字符串最大长度为3， * ......其中最大的回文子串是以str[3]=='c'为中心的时候。这种方法非常容易理解，只要解决奇回文和偶回文寻找方式的不同就可 * 以。比如"121"是奇回文，有确定的轴'2'。"1221"是偶回文，没有确定的轴，回文的虚轴在"22"中间。但是这种方法有明显的问题， * 之前遍历过的字符完全无法指导后面遍历的过程，也就是对每个字符来说都是从自己的位置出发，往左右两个方向扩出去检查。这样， * 对每个字符来说，往外扩的代价都是一个级别的。举一个极端的例子"aaaaaaaaaaaaaaa"，对每一个'a'来讲，都是扩到边界才停止。 * 所以每一个字符扩出去检查的代价都是O(N)，所以总的时间复杂度为O(N^2)。Manacher算法可以做到O(N)的时间复杂度，精髓是之 * 前字符的"扩"过程，可以指导后面字符的"扩"过程，使得每次的"扩"过程不都是从无开始。以下是Manacher算法解决原问题的过程： * * 1.因为奇回文和偶回文在判断时比较麻烦，所以对str进行处理，把每个字符开头、结尾和中间插入一个特殊字符'#'来得到一个新的 * 字符串数组。比如str="bcbaa”，处理后为〝#b#c#b#a#a#"，然后从每个字符左右扩出去的方式找最大回文子串就方便多了。对奇 * 回文来说，不这么处理也能通过扩的方式找到，比如"bcb"，从'c'开始向左右两侧扩出去能找到最大回文。处理后为"#b#c#b#"，从 * 'c'开始向左右两侧扩出去依然能找到最大回文。对偶回文来说，不处理而直接通过扩的方式是找不到的，比如"aa"，因为没有确定的 * 轴，但是处理后为"#a#a#"，就可以通过从中间的#扩出去的方式找到最大回文。所以通过这样的处理方式，最大回文子串无论是偶回 * 文还是奇回文，都可以通过统一的"扩"过程找到，解决了差异性的问题。同时要说的是，这个特殊字符是什么无所谓，甚至可以是字符 * 串中出现的字符，也不会影响最终的结果，就是一个纯辅助的作用。 * 具体的处理过程请参看如下代码中的manacherString方法。 * * 2.假设str处理之后的字符串记为charArr。对每个字符(包括特殊字符)都进行"优化后"的扩过程。在介绍"优化后"的扩过程之前， * 先解释如下三个辅助变量的意义。 * •数组pArr。长度与charArr长度一样。pArr[i]的意义是以i位置上的字符(charArr[i])作为回文中心的情况下，扩出去得到的最 * 大回文半径是多少。举个例子来说明，对"#c#a#b#a#c#"來说，pArr[0..9]为[1,2,1,2,1,6,1,2,1,2,1]。我们的整个过程就 * 是在从左到右遍历的过程中，依次计算每个位置的最大回文半径值。 * •整数pR。这个变量的意义是之前遍历的所有字符的所有回文半径中，最右即将到达的位置。还是以"#c#a#b#a#c#"为例来说，还没 * 遍历之前pR，初始设置为-1。charArr[0]=='#'的回文半径为1，所以目前回文半径向右只能扩到位置0，回文半径最右即将到达的 * 位置变为1(pR=1)。charArr[1]=='#'的回文半径为2，此时所有的回文半径向右能扩到位置2，所以回文半径最右即将到达的位置 * 变为3(pR=3)。charAr[2]=='#'的回文半径为1，所以位置2向右只能扩到位置2，回文半径最右即将到达的位置不变，仍是3 * (pR=3)。charArr[3]=='a'的回文半径为2，所以位置3向右能扩到位置4，所以回文半径最右即将到达的位置变为5(pR=5)。 * charArr[4]=='#'的回文半径为1，所以位置4向右只能扩到位置4，回文半径最右即将到达的位置不变仍是5(pR=5)。 * charArr[5]=='b'的回文半径为6，所以位置4向右能扩到位置10，回文半径最右即将到达的位置变为11(pR=11)。此时已经到达整 * 个字符数组的结尾，所以之后的过程中pR将不再变化。换句话说，pR就是遍历过的所有字符中向右扩出来的最大右边界。只要右边界更 * 往右，pR就更新。 * •整数index。这个变量表示最近一次pR更新时，那个回文中心的位置。以刚刚的例子来说，遍历到charArr[O]时pR更新，index就 * 更新为0。遍历到charArr[1]时pR更新，index就更新为1......遍历到charArr[5]时pR更新，index就更新为5。之后的过程中， * pR将不再更新，所以index将一直是5。 * * 3.只要能够从左到右依次算出数组pArr每个位置的值，最大的那个值实际上就是处理后的charArr中最大的回文半径，根据最大的回 * 文半径，再对应回原字符串的话，整个问题就解决了。步骤3就是从左到右依次计算出pArr数组每个位置的值的过程。 * 1）假设现在计算到位置i的字符charArr[i]，在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”，计算到charArr[6..10]时，pR都为11，此时pR-1包住了位置6~10。 * 这种情况下，检查过程是可以获得优化的，这也是manacher算法的核心内容，如图9-14所示。 * 在图9-14中，位置i是要计算回文半径(pArr[i])的位置。pR-1位置此时是包住位罝i的。同时根据index的定义，index是pR更新 * 时那个回文中心的位置，所以如果pR-1位置以index为中心对称，即图9-14中的"左大"位置，那么从"左大"位置到pR-1位置一定是 * 以index为中心的回文串，我们把这个回文串叫作大回文串，同时把pR-1位置称为"右大"位置。既然回文半径数组pArr是从左到右计 * 算的，所以位置i之前的所有位置都已经算过回文半径。假设位置i以index为中心向左对称过去的位置为i，那么位置i的回文半径也是 * 计算过的。那么以i为中心的最大回文串大小(pArr[i'])必然只有三种情况，我们依次来分析一下，假设以i为中心的最大回文串的左 * 边界和右边界分别记为"左小"和"右小"。 * * 情況一，"左小"和"右小"完全在"左大"和"右大"内部，即以i'为中心的最大回文串完全在以index为中心的最大回文串的内部，如图 * 9-15所示。 * 图9-15中，a'是"左小"位置的前一个字符，b'是"右小"位置的后一个字符，b是b'以index为中心的对称字符，a是a'以index为中 * 心的对称字符。"左小'"是"左小"以index为中心的对称位置，"右小'"是"右小"以index为中心的对称位置。如果处在情况一下，那 * 么以位置i为中心的最大回文串可以直接确定，就是从"右小'"到"左小'"这一段。这是什么原因呢？首先，"左小"到"右小"这一段如 * 果以index为回文中心，对应过去就是"右小'"到"左小'"这一段，那么"右小'"到"左小'"这一段就完全是"左小"到"右小"这一段的 * 逆序。同时有"左小"到"右小"这一段又是回文串(以i为回文中心)，所以"右小'"到"左小'"这一段一定也是回文串，也就是说，以位 * 置i为中心的最大回文串起码是"右小'"到"左小'"这一段。另外，以位置i'为中心的最大回文串只是"右小'"到"左小'"这一段，说明 * a'!=b'。那么与a'相等的a也必然不等于与b'相等的b，既然a!=b，说明以位置i为中心的最大回文串就是"右小'"到"左小'"这一段， * 而不会扩得更大。 * 情况一举例如图9-16所示。 * * 情况二，"左小"和"右小"的左侧部分在"左大"和"右大"的外部，如图9-17所示。 * 图9-17中，a是"左大"位置的前一个字符，d是"右大"位置的后一个字符，"左大'"是"左大"以位置i为中心的对称位置，"右大'"是 * "右大"以位置i为中心的对称位置，b是"左大'"位置的后一个字符，c是"右大'"位置的前一个字符。如果处在情况二下，那么以位置 * i为中心的最大回文串可以直接确定，就是从"右大'"到"右大"这一段。这是什么原因呢？首先"左大"到"左大'"这一段和"右大'"到 * "右大"这一段是关于index对称的，所以"右大'"到"右大"这一段是"左大"到"左大'"这一段的逆序。同时"左小"到"右小"这一段是 * 回文串(以i位置为中心)，那么"左大"到"左大'"这一段也是回文串，所以"左大〞到"左大'"这一段的逆序也是回文串，所以"右大'" * 到"右大"这一段一定是回文串。也就是说，以位置i为中心的最大回文串起码是"右大'"到"右大"这一段。另外，"左小"到"右小"这一 * 段的是回文串，说明a==b，b和c关于index对称说明b==c,"左大"到"右大〞这一段没有扩得更大，说明a!=d，所以d!=c。说明以 * 位置i为中心的最大回文串就是"右大'"到"右大"这一段，而不会扩得更大。 * 情况二举例如图9-18所示。 * * 情况三，"左小"和"左大"是同一个位置，即以i为中心的最大回文串压在了以index为中心的最大回文串的边界上，如图9-19所示。 * 图9-19中，"左大"与"左小"的位置重叠，"右小'"是"右小"位置以index为中心的对称位置，"右大'"是"右大"位置以i为中心的对 * 称位置，可以很容易的证明"右小'"和"右大'"位置也重叠。如果处在情况三下，那么以位置i为中心的最大回文串起码是"右大'"和 * "右大"这一段，但可能会扩得更大。因为"右大'"和"右大"这一段是"左小"和"右小"这一段以index为中心对称过去的，所以两段互 * 为逆序关系，同时"左小"和"右小"这一段又是回文串，所以"右大'"和"右大"这一段肯定是回文串，但以位置i为中心的最大回文串是 * 可能扩得更大的。比如图9-20的例子。 * 图9-20中，以位置i为中心的最大回文串起码是"右大'"到"右大"这一段，但可以扩得更大。说明在情况三下，扩出去的过程可以得到 * 优化，但还是无法避免扩出去的检查。 * * 4.按照步骤3的逻辑从左到右计算出pArr数组，计算完成后再遍历一遍pArr数组，找出最大的回文半径，假设位置i的回文半径最大， * 即pArr[i]==max。但max只是charArr的最大回文半径，还得对应回原来的字符串，求出最大回文半径的长度(其实就是max-1)。 * 比如原字符串为"121"，处理成charArr之后为"#1#2#1#"。在charArr中位置3的回文半径最大，最大值为4(即pArr[3]==4)， * 对应原字符串的最大回文子串长度为4-1=3。 * * Manacher算法时间复杂度是O(N)的证明。虽然我们可以很明显地看到Manacher算法与普通方法相比，在扩出去检查这一行为上有明 * 显的优化，但如何证明该算法的时间复杂度就是O(N)呢？关键之处在于估算扩出去检查这一行为发生的数量。原字符串在处理后的长度 * 由N变为2N，从步骤3的主要逻辑来看，要么在计算一个位置的回文半径时完全不需要扩出去检查，比如，步骤3的中3）介绍的情况一 * 和情况二，都可以直接获得位置i的回文半径长度；要么每一次扩出去检查都会导致pR变量的更新，比如步骤3中的2）和3）介绍的情 * 况三，扩出去检查时都让回文半径到达更右的位置，当然会使pR更新。然而pR最多是从-1增加到2N(右边界)，并且从来不减小，所以 * 扩出去检查的次数就是O(N)的级别。所以Manacher算法时间复杂度是O(N)。具体请参看如下代码中的maxLcpsLength方法。 * * @author Created by LiveEveryDay */ public class ManacherAlgorithm1 { public static char[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = new char[str.length() * 2 + 1]; int index = 0; for (int i = 0; i != res.length; i++) { res[i] = (i & 1) == 0 ? '#' : charArr[index++]; } return res; } public static int maxLcpsLength(String str) { if (str == null || str.length() == 0) { return 0; } char[] charArr = manacherString(str); int[] pArr = new int[charArr.length]; int index = -1; int pR = -1; int max = Integer.MIN_VALUE; for (int i = 0; i != charArr.length; i++) { pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1; while (i + pArr[i] < charArr.length && i - pArr[i] > -1) { if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) { pArr[i]++; } else { break; } } if (i + pArr[i] > pR) { pR = i + pArr[i]; index = i; } max = Math.max(max, pArr[i]); } return max - 1; } public static void main(String[] args) { String str = "abc1234321ab"; System.out.printf("The longest palindrome substring length is: %d", maxLcpsLength(str)); } } // ------ Output ------ /* The longest palindrome substring length is: 7 */