大白话 Manacher算法

2024-05-01 21:20
文章标签 算法 大白话 manacher

本文主要是介绍大白话 Manacher算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Manacher 算法

Manacher 算法简介

Manacher 算法用于解决字符串中最长回文子串最大长度问题。

解释一下：

  • 回文：这个很好理解了，就是字符串正序和逆序是相同的

    • 字符串长度为奇数时，该回文字符串一定会有个中心对称轴，例如 “abcba” 关于中间的 ‘c’ 左右对称

    • 字符串长度为偶数时，只有一个虚拟的对称轴，例如"abba"，只需要左右相同即可。

  • 子串：字符串中连续的字符序列

    • 一定注意了，必须得是连续的，例如对于字符串 “abcde”，“abc”、“bcd”…都是它的子串，但是类似"abd"、"ace"这种就不是它的子串了。

例如：

str=“123”，其中的最长回文子串为"1"、“2"或者"3”，所以返回 1。

str=“abbac”，其中的最长回文子串为"aabb"，所以返回 4。

str=“abc1234321ab”，其中的最长回文子串为"1234321"，所以返回 7。

整体思路

从左到右遍历字符串，遍历到每个字符的时候，都看看以这个字符作为中心能够产生多大的回文字符串。比如 str=“abacaba”，以 str[0]=='a’为中心的回文字符串最大长度为 1，以 str[1]==‘b’ 为中心的回文字符串最大长度为 3，……其中最大的回文子串是以 str[3]=='c’为中心的时候。

字符串预处理

上面的处理方式中会有一个问题，当回文字符串长度为偶数时，由于没有实际存在的中心轴，就没有办法通过上面方式求解了。

我们可以通过填充值的方式来避免出现偶数的回文串，可以对str 进行处理，把每个字符开头、结尾和中间插入一个特殊字符’#'来得到一个新的字符串数组。比如 str=“bcbaa”，处理后为"#b#c#b#a#a#"，然后从每个字符左右扩出去的方式找最大回文子串就方便多了。

  • 对奇回文来说，不这么处理也能通过扩的方式找到，比如"bcb"，从’c’开始向左右两侧扩出去能找到最大回文。处理后为"#b#c#b#"，从’c’开始向左右两侧扩出去依然能找到最大回文。

  • 对偶回文来说，不处理而直接通过扩的方式是找不到的，比如"aa"，因为没有确定的轴，但是处理后为"#a#a#"，就可以通过从中间的’#'扩出去的方式找到最大回文。

代码如下

    private static char[] manacherString(String s) {char[] chars = s.toCharArray();int n = (chars.length << 1) + 1;char[] ans = new char[n];int index = 0;for (int i = 0; i < n; i++) {ans[i] = (i & 1) == 0 ? '#' : chars[index++];}return ans;}

几个概念

假设 str 处理之后的字符串记为 charArr。对每个字符（包括特殊字符）都进行“优化后”的扩充过程。

为了后面能更加方便地介绍 Manacher 算法，这里先介绍几个概念。

回文半径

由于charArr中回文串长度都是奇数，那么它一定会有一个中心对称轴，回文半径就是该中心对称轴到两端的距离（包括端点）。

例如，对于"#a#b#c#b#a#"，它中心为 ‘c’，中心点+左边是 “#a#b#c”，中心点+右边是 “c#b#a#”，它们的长度都是6，因此回文半径长度是6。可以看到，如果还原为原始字符串，那么原始字符串的长度为5，因此原始回文字符串长度=回文半径-1。

再比如，对于"#a#b#b#a#"，它中心为正中间的 ‘#’，中心点+左边是 “#a#b#”，中心点+右边是 “#b#a#”，它们的长度都是5，因此回文半径长度是5。可以看到，如果还原为原始字符串，那么原始字符串的长度为4，因此也有原始回文字符串长度=回文半径-1。

所以，无论原始回文字符串长度为奇数还是偶数，它的长度都是扩展后回文半径-1。

回文半径数组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

这个变量的意义是之前遍历的所有字符的所有回文半径中，最右即将到达的位置。

还是以 “#c#a#b#a#c#” 为例来说，还没遍历之前，pR 初始设置为-1。

  • charArr[0]==‘#’：回文半径为 1，所以目前回文半径向右只能扩到位置 0，回文半径最右即将到达的位置变为 1（pR=1），此时对应的中心位置更新，也即是 c == 0。

  • charArr[1]=='c’的回文半径为 2，此时所有的回文半径向右能扩到位置 2，所以回文半径最右即将到达的位置变为 3（pR=3），此时对应的中心位置更新，也即是 c == 1。

  • charArr[2]=='#'的回文半径为 1，所以位置 2 向右只能扩到位置 2，回文半径最右即将到达的位置不变，仍是 3（pR=3），c不变。

  • charArr[3]=='a’的回文半径为 2，所以位置 3 向右能扩到位置 4，回文半径最右即将到达的位置变为 5（pR=5），此时对应的中心位置更新，也即是 c == 3。

  • charArr[4]=='#'的回文半径为 1，所以位置 4 向右只能扩到位置 4，回文半径最右即将到达的位置不变，仍是 5（pR=5），c不变。

  • charArr[5]=='b’的回文半径为 6，所以位置 4 向右能扩到位置 10，回文半径最右即将到达的位置变为 11（pR=11），此时对应的中心位置更新，也即是 c == 5。此时已经到达整个字符数组的结尾，所以之后的过程中pR 和c也都将不再变化。

换句话说，pR 就是遍历过的所有字符中向右扩出来的最大右边界。只要右边界更往右，pR 就更新。

image

算法流程

主流程

只要能够从左到右依次算出数组 pArr 每个位置的值，最大的那个值实际上就是处理后的 charArr 中最大的回文半径，根据最大的回文半径，再对应回原字符串，整个问题就解决了。

假设现在计算到位置 index 的字符 charArr[i]，在 i 之前位置的计算过程中，都会不断地更新pR 和 c 的值，即位置 index 之前的 c 这个回文中心扩出了一个目前最右的回文边界 pR。

再次强调一下，pR是c点所在回文区域最右侧+1的位置

走到index会有以下几种情况：

情况1：index < pR，此时，之前的回文串已经罩不住index了

image

情况2：index >= pR，此时，之前的回文串还能罩住index

此时 i 关于 c 的对称点为 i’，此时又可以分为以下三种情况

image

情况2-1：i’ 的回文半径覆盖区域（下图绿色区域）还仍在c覆盖区域内部

image

情况2-2：i’ 的回文半径覆盖区域（下图绿色区域）已经越过了 c 点覆盖的区域

image

情况2-3：i’ 的回文半径覆盖区域（下图绿色区域）刚好到达c点覆盖区域的左侧

image

具体分析

情况1：之前的回文串已经罩不住index

此时，没有优化空间，我们从 index 位置开始，向左右两侧扩出去检查，此时的“扩”过程没有获得加速。

情况2-1：之前的回文串能罩住index，i’ 回文范围未到达c回文范围左侧

我们假设i’ 回文半径覆盖范围，记做A，A左边为a位置，右边为b位置

那么一定可以在 i 周围画一个和 i’ 回文半径覆盖相同半径的区域，记做X，假设X区域左边是x位置，右边是y位置。

那么由于原始字符串关于c在 left ~ pr-1 范围内都是对称的，则 A 区域与 X 区域构成的字符串必然是逆序的，又因为 A 区域关于 i’ 是对称的，那么 X 区域一定是关于 i 对称的。则pArr[i] 至少与 pArr[i’] 是相等的。

那么 pArr[i] 能不能 > pArr[i’] 呢？答案是不能的。

我们假设 pArr[i] > pArr[i’]，则必然有 x 位置的值 == y位置的值

由于对称性，a位置的值 == y 位置的值，b位置的值 == x 位置的值

那么可以得到 a位置的值 == b 位置的值，阔到了i’ 回文覆盖的范围外面了，明显矛盾了。

image

也就是说，这种情况下，pArr[i] = pArr[i’]，且 pR以及c 都不变

情况2-2：之前的回文串能罩住index，i’ 回文范围越过了c回文范围左侧

我们假设c覆盖的回文的最左侧为 left 位置，left位置左边为a位置（a=left-1），a关于i’的对称位置为b。

再假设pr指向的位置为y位置，y关于i对称的位置为x。

现在要证明 pArr[i] == pr - index。

首先，由于i’的范围已经越过 left 了，在 left ~ pr-1范围内 i 与 i’ 又是对称的，那么i点的回文半径必定是可以取到 pr - index 的。

现在来证明 pArr[i] 不可能 > pr - index。

还是采用反证法，如果可i的回文半径可以 > pr - index，那么y位置的值 == x位置的值

由于 c 的回文范围为 left~pr-1（也就是y-1），那么a位置的值必然 != y位置的值

而由于对称性 a位置的值 == b位置的值 == x位置的值，于是得到：

x位置的值 != y位置的值，这与前面的假设是矛盾的，因此 pArr[i] = pr - index 成立。

image

这种情况下，pR与c也不用进行更新。

情况2-3：之前的回文串能罩住index，i’ 回文范围正好到达c回文范围左边界

这种情况下，无法直接获得答案，需要对 i 的回文范围进行扩充

由于对称性，我们知道 pArr[i] >= pr - index，于是可以将半径从 pr - index + 1 开始逐一比较 i 的左右字符是否相等，直到取到最大的回文半径。

image

代码实现

逐行翻译上面的实现思路，代码如下

    public static int manacher(String s) {if (s == null || s.isEmpty()) {return 0;}char[] str = manacherString(s);int n = str.length;// 之前遍历的所有字符的所有回文半径中，最右即将到达的位置的下一个位置// 一开始 pR 还没有扩充，指向-1int pR = -1;// 当前 pR 对应的中心回文子串的中心位置int c = -1;// 记录每个位置的回文半径int[] pArr = new int[n];// 记录回文半径的最大值int max = 0;// 临时变量int r;for (int index = 0; index < n; index++) {if (index < pR) { // 当前最右点可以包住 index// 3  4  5  6  7  8  9  10  11  12//       i'    c     i          pR// i' 正好到达 L 时，半径应当为 pR - iint rRange = pR - index;// i 关于 c 的对称点int iLeft = 2 * c - index;if (pArr[iLeft] < rRange) { // i'的半径 在 [L..R] 内部，不用扩pArr[index] = pArr[iLeft];// 半径 小于 c 半径，max不用更新} else if (pArr[iLeft] > rRange) { // i'的半径 在 [L..R] 外部，不用扩pArr[index] = rRange;// 半径 小于 i‘ 半径，max不用更新} else {// 接着扩，半径至少为 rangeR 了r = rRange;while (index - r > -1 && index + r < n && str[index - r] == str[index + r]) {r++;}pArr[index] = r;max = Math.max(max, r);}} else { // 当前最右点可以包不住 index// 3  4  5  6  7  8  9  10  11  12  13  14  15  16//                              pR      i// 一次也匹配不上时的半径也应当为1r = 1;while (index - r > -1 && index + r < n && str[index - r] == str[index + r]) {r++;}pArr[index] = r;max = Math.max(max, r);}// 更新 pRif (index + pArr[index] > pR) {pR = index + pArr[index];c = index;}}return max - 1;}

当然，上面这段代码在结构上还能略做优化

我们可以将这四种情况都抽象为下面过程：

  • 初始化一个 回文半径

  • 迭代获取最大回文半径（如果有必要）

  • 更新 pArr

  • 更新 pR 以及 c（如果有必要）

    public static int manacher(String s) {if (s == null || s.isEmpty()) {return 0;}char[] str = manacherString(s);int n = str.length;int pR = -1;int c = -1;int[] pArr = new int[n];int max = 0;int r = 0;for (int index = 0; index < n; index++) {// 情况1: r = 1// 情况2-1: r = pArr[2 * c - index]// 情况2-2: 情况2-3: r = pR - indexr = index < pR ? Math.min(pR - index, pArr[2 * c - index]) : 1;// 情况1、情况2-3才会走进这个循环，然后扩充r// 情况2-3以及情况2-2直接略过while (index + r < n && index - r > -1 && str[index - r] == str[index + r]) {r++;}// 填充 pArrpArr[index] = r;max = Math.max(max, r);// 如有必要（情况1、情况2-3），更新 pR 以及 cif (index + pArr[index] > pR) {pR = index + pArr[index];c = index;}}return max - 1;}

时间复杂度

分析迭代过程，对于情况 2-1 以及 情况 2-2，都只需要有限步都能获取答案，由于 index 取值从 0~n 单增，那么走到这两个分支的情况下，最多只需要 O(n) 的复杂度。

再来看 情况1 以及 情况2-2 两个分支，这两个步骤中迭代次数都是将 qR 从前一个更新到 当前步的次数，而 qR 的取值范围是 -1 ~ n，因此时间复杂度也为O(n)。

由于这几个分支只会走其中一个，因此整体的时间复杂度是 O(n)。

完整代码及对数器

    public class Manacher {public static void main(String[] args) {// comp();System.out.println(longestPalindrome("cbbd"));}public static int manacher(String s) {if (s == null || s.isEmpty()) {return 0;}char[] str = manacherString(s);int n = str.length;// 之前遍历的所有字符的所有回文半径中，最右即将到达的位置的下一个位置// 一开始 pR 还没有扩充，指向-1int pR = -1;// 当前 pR 对应的中心回文子串的中心位置int c = -1;// 记录每个位置的回文半径int[] pArr = new int[n];// 记录回文半径的最大值int max = 0;// 临时变量int r = 0;for (int index = 0; index < n; index++) {r = index < pR ? Math.min(pR - index, pArr[2 * c - index]) : 1;while (index + r < n && index - r > -1 && str[index - r] == str[index + r]) {r++;}pArr[index] = r;max = Math.max(max, r);if (index + pArr[index] > pR) {pR = index + pArr[index];c = index;}}return max - 1;}public static int manacher2(String s) {if (s == null || s.isEmpty()) {return 0;}char[] str = manacherString(s);int n = str.length;// 之前遍历的所有字符的所有回文半径中，最右即将到达的位置的下一个位置// 一开始 pR 还没有扩充，指向-1int pR = -1;// 当前 pR 对应的中心回文子串的中心位置int c = -1;// 记录每个位置的回文半径int[] pArr = new int[n];// 记录回文半径的最大值int max = 0;// 临时变量int r;for (int index = 0; index < n; index++) {if (index < pR) { // 当前最右点可以包住 index// 3  4  5  6  7  8  9  10  11  12//       i'    c     i          pR// i' 正好到达 L 时，半径应当为 pR - iint rRange = pR - index;// i 关于 c 的对称点int iLeft = 2 * c - index;if (pArr[iLeft] < rRange) { // i'的半径 在 [L..R] 内部，不用扩pArr[index] = pArr[iLeft];// 半径 小于 c 半径，max不用更新} else if (pArr[iLeft] > rRange) { // i'的半径 在 [L..R] 外部，不用扩pArr[index] = rRange;// 半径 小于 i‘ 半径，max不用更新} else {// 接着扩，半径至少为 rangeR 了r = rRange;while (index - r > -1 && index + r < n && str[index - r] == str[index + r]) {r++;}pArr[index] = r;max = Math.max(max, r);}} else { // 当前最右点可以包不住 index// 3  4  5  6  7  8  9  10  11  12  13  14  15  16//                              pR      i// 一次也匹配不上时的半径也应当为1r = 1;while (index - r > -1 && index + r < n && str[index - r] == str[index + r]) {r++;}pArr[index] = r;max = Math.max(max, r);}// 更新 pRif (index + pArr[index] > pR) {pR = index + pArr[index];c = index;}}return max - 1;}/*** 扩展字符串，abba => #a#b#b#a#* <p>主要是可以将偶数个数的回文串转换为奇数个中心对称的回文串，方便统一处理*/private static char[] manacherString(String s) {char[] chars = s.toCharArray();int n = (chars.length << 1) + 1;char[] ans = new char[n];int index = 0;for (int i = 0; i < n; i++) {ans[i] = (i & 1) == 0 ? '#' : chars[index++];}return ans;}/*** for test：暴力解，求解每一个位置的回文字符串的长度，时间复杂度O(n^2)*/public static int right(String s) {if (s == null || s.isEmpty()) {return 0;}char[] str = manacherString(s);int max = 0;for (int i = 0; i < str.length; i++) {int l = i - 1;int r = i + 1;while (l >= 0 && r < str.length && str[l] == str[r]) {l--;r++;}max = Math.max(max, r - l - 1);}return max / 2;}/*** for test*/public static String getRandomString(int possibilities, int size) {char[] ans = new char[(int) (Math.random() * size) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');}return String.valueOf(ans);}private static void comp() {int possibilities = 25;int strSize = 20;int testTimes = 5000000;System.out.println("test begin");for (int i = 0; i < testTimes; i++) {String str = getRandomString(possibilities, strSize);int ans1 = manacher(str);int ans2 = manacher2(str);int ans3 = right(str);if (ans1 != ans2 || ans1 != ans3) {System.out.println(str);System.out.println(ans1);System.out.println(ans2);throw new RuntimeException("Oops!");}}System.out.println("test finish");}}

参考资料

https://www.bilibili.com/video/BV1YH4y1h7MU/

https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

这篇关于大白话 Manacher算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/952697。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
最大公因数：欧几里得算法

最大公因数：欧几里得算法

简述         求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行 m=n，n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为：6 代码实现 #include<iostream>using namespace std;/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2