马拉车算法（Manacher’s algorithm）

avatar
Administrator

2024-08-27

32
0

回文介绍

回文就是正读倒读都一样的字符串，如 “level”, “noon”

求最长回文串，需要遍历去求以每个字符为中心，向两边寻找回文子串
获得最大回文子串的时间复杂度 O(n^2)

而马拉车算法的时间复杂度为 O(n)

马拉车算法

1、预处理

解决奇偶数回文问题）在每一个字符的左右都加上一个特殊字符，如 #

level   ->  #l#e#v#e#l#
noon    ->  #n#o#o#n#

处理之后得到的字符串的个数都是奇数个，之前是回文的之后还是回文，不用分情况讨论了

2、求回文子串的半径

处理之后得到的字符串 t
                    #  a  #  a  #  b  #  b  #  a  #  b  #  b  #  a  #
位置 i
                    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
以 t[i] 字符为中心的回文子串半径数组 p
                    1  2  3  2  1  2  5  2  1  8  1  2  5  2  1  2  1

怎么计算呢？
如位置 9 的字符是 a，本身算 1，因为 a 字符串本身就是对称的
然后比较 a 左右的字符，相同则 p[9]++，不断向外扩展，最后得到 p[9] = 8

求回文子串的半径有什么用？
以 t[9] = a 为中心的回文是 #a#b#b#a#b#b#a#，原字符串回文 abbabba 长度 7
刚好是 p[9] - 1，即回文子串的半径减 1（#a#b#b#a#b#b#a#）
这是个通用规律，可以思考、去求证下

算法核心介绍

引入两个辅助变量 mx 和 id
mx 是之前计算中最长回文子串的右端点的最大值
id 为取得 mx 的回文中心位置

mx > i

p[2 * id - i]   对称点 j 的回文子串的半径
mx - i    

如果 p[2 * id - i] < j - mx' = mx - i
    根据对称性，即以 j 为中心的回文包含在以 id 为中心的回文里面
    id 到 mx、mx' 左右对称

    ==> p[i] = p[j] = p[2 * id - i]

mx > i

如果 p[2 * id - i] >= j - mx' = mx - i
    表示 i 为中心的回文右边界超过了 mx
    因为 mx 右侧的字符是未计算的，需要再循环比较

    ==> p[i] = mx - i

i > mx

无法对 p[i] 做更多的假设，只能 p[i] = 1，然后再去匹配了

算法核心代码

p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

具体实现

package main

import (
    "bytes"
    "fmt"
    "strings"
)

func main() {
    s := "aabbabba"
    fmt.Println(manacher(s))
    // abbabba
}

// 马拉车算法
func manacher(s string) string {
    char := byte('#')
    s = changeStr(s, char)

    // 存储以字符 N[i] 为中心的最长回文字串的最右字符到 N[i] 的长度
    p := make([]int, len(s))
    // mx 之前计算中最长回文子串的右端点的最大值，id 为取得 mx 的回文中心位置
    var id, mx int
    // 最大回文中心位置
    maxCenterIndex := 1

    // 去除边界 ^ $
    for i := 1; i < len(p) - 1; i++ {
        // j 是 i 以 id 为中心的对称点
        j := 2 * id - i

        // i 处在右边界 mx 的左边
        if mx > i {
            if mx - i > p[j] {  // 对称点 j 的回文串没有越界，根据对称关系赋值
                p[i] = p[j]
            } else {            // 越界，则先赋值 mx - i
                p[i] = mx - i
            }
        }

        // 循环比较
        for s[i + p[i]] == s[i - p[i]] {
            p[i]++
        }

        // i 的右边界超出 mx
        if i + p[i] > mx {
            mx = i + p[i]
            id = i
        }

        // 计算最大回文中心位置
        if p[i] > p[maxCenterIndex] {
            maxCenterIndex = i
        }
    }

    // 最大回文串长度
    //maxLength := p[maxCenterIndex] - 1

    // 返回最长回文
    start := maxCenterIndex - p[maxCenterIndex] + 1
    end := maxCenterIndex + p[maxCenterIndex]
    substr := s[start:end]

    return strings.Replace(substr, string(char), "", -1)
}

// 改变字符串
func changeStr(s string, char byte) string {
    var new bytes.Buffer

    new.WriteByte('^')
    for _, b := range []byte(s) {
        new.WriteByte(char)
        new.WriteByte(b)
    }
    new.WriteByte(char)
    new.WriteByte('$')

    return new.String()
}


马拉车算法(Manacher算法)的原理

在求一段字符串中的最长回文子串时，Manacher算法的时间复杂度可以达到O(n)，是最优的求最长回文子串算法。简单说一下最近对这个算法原理的理解，希望对同样在看这个算法的朋友有些启发。

想一个简单方法

求一个字符串中的最长回文子串，我们最先想到的是由字符串中的每一个字符开始，向两边辐射，当前字符左右两边的字符相等，则当前字符的回文长度增加，这样可分别求出以每个字符为中心的回文子串的长度。

问题

但是回文存在偶数长度的回文（如:abba）和奇数长度的回文（如:aba），那么上面的方法只能针对奇数长度的回文而无法处理偶数长度的回文。

怎么解决

如果能将偶数回文转换成奇数回文，那么就不会有这个问题了。当我们使用一个分割符将字符串每个字符分割开时（如:abba—>#a#b#b#a#），我们发现字符串中的每个字符都变成了奇数回文，而且可以观察到以每个字符为中心的回文子串的长度=回文半径-1（比如,第一个a的回文半径为2，他实际的回文长度为1）

这样的话，我们就可以通过求出每个字符的回文半径，然后取最大值，再减去1就是最长回文子串的长度。


def func(s):
    c ="#"
    p = c+ c.join(s)+c

    cnt = len(p)
    cus = [1]*cnt

    for i in range(cnt):

        while i-cus[i] >= 0 and i+cus[i] <cnt and p[i+cus[i]] == p[i-cus[i]]:
            cus[i]+=1


    return max(cus)-1

优化？

在上面的算法中，我们对字符串中的每一个字符都从最靠近他的左右字符开始挨着比较，来计算回文半径。观察”aaaaaa”和”a121x121a”等这种类型的字符串，对于”a121x121a”这种字符串，当我们计算完以x为中心的回文字符串的长度时，我们还是会计算对称的以1,2,1,a为中心的回文子串的长度，而在中例子中我们可以观察发现右边以1,2,1,a为中心的回文子串的长度是和对称的1,2,1,a的长度相等的。如何才能利用已经计算过的部分的数据呢？

马拉车算法

如下图所示。

1.如果当前位置为i, 目前最触及右边的回文子串的最右边是mx、中心是id。则i的对称点为: j = 2*id-i

  • 2.当i<mx时，如果以i为中心的回文子串的半径小于mx-i，则他被完全包裹入以id为中心的子串中。即其回文半径==其对称点j的回文子串的回文半径。

  • 3.当i<mx,且以i为中心的回文子串的半径>=mx-i。其回文半径最短为mx-i

  • 4.当i>mx, i已经在mx的右边，i为中心的回文子串的半径无法预测，其最小长度为1.
    也就是说，当i<mx时，可以肯定的是，以i为中心的回文子串的回文半径最短也是 2 和 3 的最小值。这样就可以减少重复计算的次数 。



def func2(s):
    c ="#"
    p = c+ c.join(s)+c

    cnt = len(p)
    cus = [1]*cnt

    mx = 0
    id = 0
    for i in range(cnt):

        if i<mx:
            mirror_i = 2*id-i
            cus[i]=min(cus[mirror_i], mx-i)

        while i-cus[i] >= 0 and i+cus[i] <cnt and p[i+cus[i]] == p[i-cus[i]]:
            cus[i]+=1

        if cus[i]+i>mx:
            mx = cus[i]
            id = i


    return max(cus)-1

总结

马拉车算法主要通过给字符串加分割符来将奇偶回文都按奇回文处理。并通过在遍历奇回文中的以每个字符为中心的回文子串时，利用i<mx时可预测以i为中心的回文半径的最小大小来减少回文计算次数，实现了求解最大回文子串的最优解。

老司机开车，教会女朋友什么是「马拉车算法」


马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 ，由一个叫 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

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

第 1 行数组 char ：原始字符串加上分隔符以后的每个字符。

第 2 行数组 index ：这个数组是新字符串的索引数组，它的值是从 0 开始的索引编号。

  • 我们首先填 p[0]。

以 char[0] = '#' 为中心，同时向左边向右扩散，走 1 步就碰到边界了，因此能扩散的步数为 0，因此 p[0] = 0；

  • 下面填写 p[1] 。

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

char

#

a

#

b

#

b

#

a

#

b

#

b

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

0

1

  • 下面填写 p[2] 。

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

char

#

a

#

b

#

b

#

a

#

b

#

b

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

0

1

0

  • 下面填写 p[3]。

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

char

#

a

#

b

#

b

#

a

#

b

#

b

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

0

1

0

1

  • 下面填写 p[4]。

以 char[4] = '#' 为中心，同时向左边向右扩散，最多可以走 4 步，左边到达左边界，因此 p[4] = 4。

char

#

a

#

b

#

b

#

a

#

b

#

b

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

0

1

0

1

4

  • 继续填完 p 数组剩下的部分。

分析到这里，后面的数字不难填出，最后写成如下表格：

char

#

a

#

b

#

b

#

a

#

b

#

b

#

index

0

1

2

3

4

5

6

7

8

9

10

11

12

p

0

1

0

1

4

1

0

5

0

1

2

1

0

说明：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字符的偏差，本质上是一样的。

下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的  “最长回文子串” ："bbabb"。这个结论具有一般性，即：

辅助数组 `p` 的最大值就是“最长回文子串”的长度

因此，我们可以在计算辅助数组 p 的过程中记录这个最大值，并且记录最长回文子串。

简单说明一下这是为什么：

如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

因为最后一定以分隔符结尾，还要计算一个，正好这个就可以把原始回文子串的中心算进去；

如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符  # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

因此，“辅助数组 p 的最大值就是“最长回文子串”的长度”这个结论是成立的，可以看下面的图理解上面说的 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 的镜像点的步数


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

情况 2（2）：p[mirror] 的数值恰好等于 maxRight - i。

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

  1. 因为靠左边的 f 与靠右边的 g 的原因，导致“以 center 为中心的回文子串”不能继续扩散；

  2. 但是“以 i 为中心的回文子串” 还可以继续扩散。

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

情况 2（3）：p[mirror] 的数值大于 maxRight - i。

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

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

最后，再推荐一篇用漫画的形式讲解马拉车算法的文章：漫画：如何找到字符串中的最长回文子串？