您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

什么是「马拉车算法」

时间:2020-05-06 11:40:07  来源:  作者:

马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 ,由一个叫 Manacher 的人在 1975 年发明的,这个方法的牛逼之处在于将时间复杂度提升到了 线性 。

事实上,马拉车算法在思想上和 KMP 字符串匹配算法有相似之处,都避免做了很多重复的工作。

如果你觉得马拉车算法的中文称呼有点俗,那么 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[0] = '#' 为中心,同时向左边向右扩散,走 1 步就碰到边界了,因此能扩散的步数为 0,因此 p[0] = 0;

char#a#b#b#a#b#b#index0123456789101112p0

  • 下面填写 p[1] 。

以 char[1] = 'a' 为中心,同时向左边向右扩散,走 1 步,左右都是 "#",构成回文子串,于是再继续同时向左边向右边扩散,左边就碰到边界了,最多能扩散的步数”为1,因此 p[1] = 1;

char#a#b#b#a#b#b#index0123456789101112p01

  • 下面填写 p[2] 。

以 char[2] = '#' 为中心,同时向左边向右扩散,走 1 步,左边是 "a",右边是"b",不匹配,最多能扩散的步数为 0,因此 p[2] = 0;

char#a#b#b#a#b#b#index0123456789101112p010

  • 下面填写 p[3]。

以 char[3] = 'b' 为中心,同时向左边向右扩散,走 1 步,左右两边都是 “#”,构成回文子串,继续同时向左边向右扩散,左边是 "a",右边是 "b",不匹配,最多能扩散的步数为 1 ,因此 p[3] = 1;

char#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 ,它们分别的含义如下:

maxRight

maxRight 表示记录当前向右扩展的最远边界,即从开始到现在使用“中心扩散法”能得到的回文子串,它能延伸到的最右端的位置 。

对于 maxRight 我们说明 3 点:

  1. “向右最远”是在计算辅助数组 p 的过程中,向右边扩散能走的索引最大的位置,注意:得到一个 maxRight 所对应的回文子串,并不一定是当前得到的“最长回文子串”,很可能的一种情况是,某个回文子串可能比较短,但是它正好在整个字符串比较靠后的位置;
  2. maxRight 的下一个位置可能是被程序看到的,停止的原因有 2 点:(1)左边界不能扩散,导致右边界受限制也不能扩散,maxRight 的下一个位置看不到;(2)正是因为看到了 maxRight 的下一个位置,导致 maxRight 不能继续扩散。
  3. 为什么 maxRight 很重要?因为扫描是从左向右进行的, maxRight 能够提供的信息最多,它是一个重要的分类讨论的标准,因此我们需要一个变量记录它。

center

center 是与 maxRight 相关的一个变量,它是上述 maxRight 的回文中心的索引值。对于 center 的说明如下:

center 的形式化定义:

什么是「马拉车算法」

 

说明:x + p[x] 的最大值就是我们定义的 maxRight,i 是循环变量,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 种情况:

情况 2(1):p[mirror] 的数值比较小,不超过 maxRight - i。

说明:maxRight - i 的值,就是从 i 关于 center 的镜像点开始向左走(不包括它自己),到 maxRight 关于 center 的镜像点的步数

什么是「马拉车算法」

 

五分钟学算法:Manacher 算法分类讨论情况 2(1)

从图上可以看出,由于“以 center 为中心的回文子串”的对称性,导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性,“以 i 为中心的回文子串”与“以 center 为中心的回文子串”不能再扩散了,此时,直接把数值抄过来即可,即p[i] = p[mirror]。

情况 2(2):p[mirror] 的数值恰好等于 maxRight - i。

什么是「马拉车算法」

 

五分钟学算法:Manacher 算法分类讨论情况 2(2)

说明:仍然是依据“以 center 为中心的回文子串”的对称性,导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。

  1. 因为靠左边的 f 与靠右边的 g 的原因,导致“以 center 为中心的回文子串”不能继续扩散;
  2. 但是“以 i 为中心的回文子串” 还可以继续扩散。

因此,可以先把 p[mirror] 的值抄过来,然后继续“中心扩散法”,继续增加maxRight。

情况 2(3):p[mirror] 的数值大于 maxRight - i。

什么是「马拉车算法」

 

五分钟学算法:Manacher 算法分类讨论情况 2(3)

说明:仍然是依据“以 center 为中心的回文子串”的对称性,导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。下面证明,p[i] = maxRight - i ,证明的方法还是利用三个回文子串的对称性。

什么是「马拉车算法」

 

五分钟学算法:Manacher 算法分类讨论情况 2(3)的证明

① 由于“以 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 算法我个人觉得没有必要记住,如果真有遇到,查资料就可以了。



Tags:拉车算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
马拉车算法( Manacher&lsquo;s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 ,由一个叫 Manacher 的人在 197...【详细内容】
2020-05-06  Tags: 拉车算法  点击:(59)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条