广德县建设协会网站,网站头像设计免费制作,马鞍山网站建设,做网站的技术关键戳蓝字“CSDN云计算”关注我们哦#xff01;作者 | 李威责编 | 阿秃马拉车算法#xff08; Manacher‘s Algorithm #xff09;是小吴最喜欢的算法之一#xff0c;因为#xff0c;它真的很牛逼#xff01;马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 …戳蓝字“CSDN云计算”关注我们哦作者 | 李威责编 | 阿秃马拉车算法 Manacher‘s Algorithm 是小吴最喜欢的算法之一因为它真的很牛逼马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 由一个叫 Manacher 的人在 1975 年发明的这个方法的牛逼之处在于将时间复杂度提升到了 线性 。事实上马拉车算法在思想上和 KMP 字符串匹配算法有相似之处都避免做了很多重复的工作。如果你觉得马拉车算法的中文称呼有点俗那么 KMP算法 就是带了一点颜色了你总能在有关于 KMP算法 介绍的文章留言区看到它的中文俗称。Manacher 算法本质上还是 中心扩散法 只不过它使用了类似 KMP 算法的技巧充分挖掘了已经进行回文判定的子串的特点提高算法的效率。下面介绍 Manacher 算法的运行流程。首先还是“中心扩散法”的思想回文串可分为奇数回文串和偶数回文串它们的区别是奇数回文串关于它的“中点”满足“中心对称”偶数回文串关于它“中间的两个点”满足“中心对称”。为了避免对于回文串字符个数为奇数还是偶数的套路首先对原始字符串进行预处理方法也很简单添加分隔符。第 1 步预处理 第一步是对原始字符串进行预处理也就是 添加分隔符 。首先在字符串的首尾、相邻的字符中插入分隔符例如 babad 添加分隔符 # 以后得到 #b#a#b#a#d#。对这一点有如下说明1、分隔符是一个字符种类也只有一个并且这个字符一定不能是原始字符串中出现过的字符2、加入了分隔符以后使得“间隙”有了具体的位置方便后续的讨论并且新字符串中的任意一个回文子串在原始字符串中的一定能找到唯一的一个回文子串与之对应因此对新字符串的回文子串的研究就能得到原始字符串的回文子串3、新字符串的回文子串的长度一定是奇数4、新字符串的回文子串一定以分隔符作为两边的边界因此分隔符起到“哨兵”的作用。五分钟学算法原始字符串与新字符串的对应关系第 2 步计算辅助数组 p 辅助数组 p 记录了新字符串中以每个字符为中心的回文子串的信息。手动的计算方法仍然是“中心扩散法”此时记录以当前字符为中心向左右两边同时扩散记录能够扩散的最大步数。以字符串 abbabb 为例说明如何手动计算得到辅助数组 p 我们要填的就是下面这张表。char#a#b#b#a#b#b#index0123456789101112p第 1 行数组 char 原始字符串加上分隔符以后的每个字符。第 2 行数组 index 这个数组是新字符串的索引数组它的值是从 0 开始的索引编号。我们首先填 p[0]。char#a#b#b#a#b#b#index0123456789101112p0以 char[0] # 为中心同时向左边向右扩散走 1 步就碰到边界了因此能扩散的步数为 0因此 p[0] 0下面填写 p[1] 。以 char[1] a 为中心同时向左边向右扩散走 1 步左右都是 #构成回文子串于是再继续同时向左边向右边扩散左边就碰到边界了最多能扩散的步数”为 1因此 p[1] 1char#a#b#b#a#b#b#index0123456789101112p01下面填写 p[2] 。以 char[2] # 为中心同时向左边向右扩散走 1 步左边是 a右边是 b不匹配最多能扩散的步数为 0因此 p[2] 0下面填写 p[3]。以 char[3] b 为中心同时向左边向右扩散走 1 步左右两边都是 “#”构成回文子串继续同时向左边向右扩散左边是 a右边是 b不匹配最多能扩散的步数为 1 因此 p[3] 1char#a#b#b#a#b#b#index0123456789101112p0101下面填写 p[4]。以 char[4] # 为中心同时向左边向右扩散最多可以走 4 步左边到达左边界因此 p[4] 4。char#a#b#b#a#b#b#index0123456789101112p01014继续填完 p 数组剩下的部分。分析到这里后面的数字不难填出最后写成如下表格char#a#b#b#a#b#b#index0123456789101112p0101410501210说明有些资料将辅助数组 p 定义为回文半径数组即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径包括第 i 个字符与我们这里定义的辅助数组 p 有一个字符的偏差本质上是一样的。下面是辅助数组 p 的结论辅助数组 p 的最大值是 5对应了原字符串 abbabb 的 “最长回文子串” bbabb。这个结论具有一般性即辅助数组 p 的最大值就是“最长回文子串”的长度因此我们可以在计算辅助数组 p 的过程中记录这个最大值并且记录最长回文子串。简单说明一下这是为什么如果新回文子串的中心是一个字符那么原始回文子串的中心也是一个字符在新回文子串中向两边扩散的特点是“先分隔符后字符”同样扩散的步数因为有分隔符 # 的作用在新字符串中每扩散两步虽然实际上只扫到一个有效字符但是相当于在原始字符串中相当于计算了两个字符。因为最后一定以分隔符结尾还要计算一个正好这个就可以把原始回文子串的中心算进去五分钟学算法理解辅助数组的数值与原始字符串回文子串的等价性-1如果新回文子串的中心是 #那么原始回文子串的中心就是一个“空隙”。在新回文子串中向两边扩散的特点是“先字符后分隔符”扩散的步数因为有分隔符 # 的作用在新字符串中每扩散两步虽然实际上只扫到一个有效字符但是相当于在原始字符串中相当于计算了两个字符。因此“辅助数组 p 的最大值就是“最长回文子串”的长度”这个结论是成立的可以看下面的图理解上面说的 2 点。五分钟学算法理解辅助数组的数值与原始字符串回文子串的等价性-2写到这里其实已经能写出一版代码。注本文的代码是结合了 LeetCode 第 5 题「最长回文子串」进行讲解参考代码 public class Solution { public String longestPalindrome(String s) { int len s.length(); if (len 2) { return s; } String str addBoundaries(s, #); int sLen 2 * len 1; int maxLen 1; int start 0; for (int i 0; i sLen; i) { int curLen centerSpread(str, i); if (curLen maxLen) { maxLen curLen; start (i - maxLen) / 2; } } return s.substring(start, start maxLen); } private int centerSpread(String s, int center) { // left right 的时候此时回文中心是一个空隙回文串的长度是奇数 // right left 1 的时候此时回文中心是任意一个字符回文串的长度是偶数 int len s.length(); int i center - 1; int j center 1; int step 0; while (i 0 j len s.charAt(i) s.charAt(j)) { i--; j; step; } return step; } /** * 创建预处理字符串 * * param s 原始字符串 * param divide 分隔字符 * return 使用分隔字符处理以后得到的字符串 */ private String addBoundaries(String s, char divide) { int len s.length(); if (len 0) { return ; } if (s.indexOf(divide) ! -1) { throw new IllegalArgumentException(参数错误您传递的分割字符在输入字符串中存在); } StringBuilder stringBuilder new StringBuilder(); for (int i 0; i len; i) { stringBuilder.append(divide); stringBuilder.append(s.charAt(i)); } stringBuilder.append(divide); return stringBuilder.toString(); }}复杂度分析 时间复杂度O(N2)这里 N 是原始字符串的长度。新字符串的长度是 2 * N 1不计系数与常数项因此时间复杂度仍为 O(N2)。空间复杂度O(N)。科学家的工作 此时计算机科学家 Manacher 出现了他充分利用新字符串的回文性质计算辅助数组 p。上面的代码不太智能的地方是对新字符串每一个位置进行中心扩散会导致原始字符串的每一个字符被访问多次一个比较极端的情况就是#a#a#a#a#a#a#a#a#。事实上计算机科学家 Manacher 就改进了这种算法使得在填写新的辅助数组 p 的值的时候能够参考已经填写过的辅助数组 p 的值使得新字符串每个字符只访问了一次整体时间复杂度由 O(N2) 改进到 O(N)。具体做法是在遍历的过程中除了循环变量 i 以外我们还需要记录两个变量它们是 maxRight 和 center 它们分别的含义如下maxRightmaxRight 表示记录当前向右扩展的最远边界即从开始到现在使用“中心扩散法”能得到的回文子串它能延伸到的最右端的位置 。对于 maxRight 我们说明 3 点“向右最远”是在计算辅助数组 p 的过程中向右边扩散能走的索引最大的位置注意得到一个 maxRight 所对应的回文子串并不一定是当前得到的“最长回文子串”很可能的一种情况是某个回文子串可能比较短但是它正好在整个字符串比较靠后的位置maxRight 的下一个位置可能是被程序看到的停止的原因有 2 点1左边界不能扩散导致右边界受限制也不能扩散maxRight 的下一个位置看不到2正是因为看到了 maxRight 的下一个位置导致 maxRight 不能继续扩散。为什么 maxRight 很重要因为扫描是从左向右进行的 maxRight 能够提供的信息最多它是一个重要的分类讨论的标准因此我们需要一个变量记录它。centercenter 是与 maxRight 相关的一个变量它是上述 maxRight 的回文中心的索引值。对于 center 的说明如下center 的形式化定义说明x p[x] 的最大值就是我们定义的 maxRighti 是循环变量0 x i 表示是在 i 之前的所有索引里得到的最大值 maxRight它对应的回文中心索引就是上述式子。maxRight 与 center 的关系maxRight 与 center 是一一对应的关系即一个 center 的值唯一对应了一个 maxRight 的值因此 maxRight 与 center 必须要同时更新。下面的讨论就根据循环变量 i 与 maxRight 的关系展开讨论情况 1当 i maxRight 的时候这就是一开始以及刚刚把一个回文子串扫描完的情况此时只能够根据“中心扩散法”一个一个扫描逐渐扩大 maxRight情况 2当 i maxRight 的时候根据新字符的回文子串的性质循环变量关于 center 对称的那个索引记为 mirror的 p 值就很重要。我们先看 mirror 的值是多少因为 center 是中心i 和 mirror 关于 center 中心对称因此 (mirror i) / 2 center 所以 mirror 2 * center - i。根据 p[mirror] 的数值从小到大具体可以分为如下 3 种情况情况 21p[mirror] 的数值比较小不超过 maxRight - i。说明maxRight - i 的值就是从 i 关于 center 的镜像点开始向左走不包括它自己到 maxRight 关于 center 的镜像点的步数五分钟学算法Manacher 算法分类讨论情况 21从图上可以看出由于“以 center 为中心的回文子串”的对称性导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性“以 i 为中心的回文子串”与“以 center 为中心的回文子串”不能再扩散了此时直接把数值抄过来即可即 p[i] p[mirror]。情况 22p[mirror] 的数值恰好等于 maxRight - i。五分钟学算法Manacher 算法分类讨论情况 22说明仍然是依据“以 center 为中心的回文子串”的对称性导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。因为靠左边的 f 与靠右边的 g 的原因导致“以 center 为中心的回文子串”不能继续扩散但是“以 i 为中心的回文子串” 还可以继续扩散。因此可以先把 p[mirror] 的值抄过来然后继续“中心扩散法”继续增加 maxRight。情况 23p[mirror] 的数值大于 maxRight - i。五分钟学算法Manacher 算法分类讨论情况 23说明仍然是依据“以 center 为中心的回文子串”的对称性导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。下面证明p[i] maxRight - i 证明的方法还是利用三个回文子串的对称性。五分钟学算法Manacher 算法分类讨论情况 23的证明① 由于“以 center 为中心的回文子串”的对称性 黄色箭头对应的字符 c 和 e 一定不相等② 由于“以 mirror 为中心的回文子串”的对称性 绿色箭头对应的字符 c 和 c 一定相等③ 又由于“以 center 为中心的回文子串”的对称性 蓝色箭头对应的字符 c 和 c 一定相等推出“以 i 为中心的回文子串”的对称性 红色箭头对应的字符 c 和 e 一定不相等。因此p[i] maxRight - i不可能再大。上面是因为我画的图可能看的朋友会觉得理所当然。事实上可以使用反证法证明如果“以 i 为中心的回文子串” 再向两边扩散的两个字符 c 和 e 相等就能够推出黄色、绿色、蓝色、红色箭头所指向的 8 个变量的值都相等此时“以 center 为中心的回文子串” 就可以再同时向左边和右边扩散 1 格与 maxRight 的最大性矛盾。综合以上 3 种情况当 i maxRight 的时候p[i] 可以参考 p[mirror] 的信息以 maxRight - i 作为参考标准p[i] 的值应该是保守的即二者之中较小的那个值p[i] min(maxRight - i, p[mirror]);参考代码 public class Solution { public String longestPalindrome(String s) { // 特判 int len s.length(); if (len 2) { return s; } // 得到预处理字符串 String str addBoundaries(s, #); // 新字符串的长度 int sLen 2 * len 1; // 数组 p 记录了扫描过的回文子串的信息 int[] p new int[sLen]; // 双指针它们是一一对应的须同时更新 int maxRight 0; int center 0; // 当前遍历的中心最大扩散步数其值等于原始字符串的最长回文子串的长度 int maxLen 1; // 原始字符串的最长回文子串的起始位置与 maxLen 必须同时更新 int start 0; for (int i 0; i sLen; i) { if (i maxRight) { int mirror 2 * center - i; // 这一行代码是 Manacher 算法的关键所在要结合图形来理解 p[i] Math.min(maxRight - i, p[mirror]); } // 下一次尝试扩散的左右起点能扩散的步数直接加到 p[i] 中 int left i - (1 p[i]); int right i (1 p[i]); // left 0 right sLen 保证不越界 // str.charAt(left) str.charAt(right) 表示可以扩散 1 次 while (left 0 right sLen str.charAt(left) str.charAt(right)) { p[i]; left--; right; } // 根据 maxRight 的定义它是遍历过的 i 的 i p[i] 的最大者 // 如果 maxRight 的值越大进入上面 i maxRight 的判断的可能性就越大这样就可以重复利用之前判断过的回文信息了 if (i p[i] maxRight) { // maxRight 和 center 需要同时更新 maxRight i p[i]; center i; } if (p[i] maxLen) { // 记录最长回文子串的长度和相应它在原始字符串中的起点 maxLen p[i]; start (i - maxLen) / 2; } } return s.substring(start, start maxLen); } /** * 创建预处理字符串 * * param s 原始字符串 * param divide 分隔字符 * return 使用分隔字符处理以后得到的字符串 */ private String addBoundaries(String s, char divide) { int len s.length(); if (len 0) { return ; } if (s.indexOf(divide) ! -1) { throw new IllegalArgumentException(参数错误您传递的分割字符在输入字符串中存在); } StringBuilder stringBuilder new StringBuilder(); for (int i 0; i len; i) { stringBuilder.append(divide); stringBuilder.append(s.charAt(i)); } stringBuilder.append(divide); return stringBuilder.toString(); }}复杂度分析 时间复杂度O(N)由于 Manacher 算法只有在遇到还未匹配的位置时才进行匹配已经匹配过的位置不再匹配因此对于字符串 S 的每一个位置都只进行一次匹配算法的复杂度为 O(N)。空间复杂度O(N)。后记 Manacher 算法我个人觉得没有必要记住如果真有遇到查资料就可以了。福利扫描添加小编微信备注“姓名公司职位”入驻【CSDN博客】加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读
