喜迎
春节

马拉车算法（Manacher's Algorithm）详解

PHP 马拉车算法 Manacher
算法
发布日期:   2024-11-21
文章字数:   790
阅读时长:   3 分

什么是马拉车算法？

马拉车算法是一种高效查找一个字符串的最长回文子串的线性时间复杂度算法。它通过巧妙的预处理和动态规划，避免了大量的重复计算，使得算法的效率得到了极大的提升。
注：回文（Palindrome）是指正读和反读都一样的字符串，即左右对称的字符串，如：level，noon，232…

算法核心思想

  • 预处理:
    • 在字符串的每个字符之间插入一个特殊字符（如#），使得原字符串变为奇数长度。这样，无论是奇数长度还是偶数长度的回文子串，都可以统一处理成奇数长度的回文子串。
  • 中心扩展:
    • 从字符串的第一个字符开始，向两边扩展，找到以当前字符为中心的回文子串的最长长度。
  • 利用对称性:
    • 算法的关键在于利用已经计算过的回文子串的信息，来加速后续回文子串的查找。通过对称性，可以减少不必要的字符比较。

算法实现步骤

  1. 预处理: 将原字符串转换为一个新的字符串，在每个字符之间插入一个特殊字符。
  2. 初始化数组P: 数组P用来存储以每个字符为中心的最长回文子串的半径。
  3. 遍历预处理后的字符串:
    • 维护一个中心id和最右边界mx。
    • 对于当前字符i，利用对称性，可以快速得到一个初始的回文半径。
    • 然后，以i为中心，向两边扩展，直到遇到不匹配的字符或者到达边界。
    • 更新P[i]，以及中心id和最右边界mx。

代码示例（php）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function longestPalindrome($s) {
    $n = strlen($s);
    $T = '#';
    for ($i = 0; $i < $n; $i++) {
        $T .= $s[$i] . '#';
    }
    $n = strlen($T);
    $p = array_fill(0, $n, 0);		// 创建数组 p，用于存储以每个位置为中心的最长回文半径。
    $center = 0;
    $right = 0;

    for ($i = 1; $i < $n - 1; $i++) {
        $mirror = 2 * $center - $i;
        $p[$i] = ($i < $right) ? min($right - $i, $p[$mirror]) : 1;

        while ($i + $p[$i] < $n && $i - $p[$i] > 0 && $T[$i + $p[$i]] == $T[$i - $p[$i]]) {
            $p[$i]++;
        }

        if ($i + $p[$i] - 1 > $right) {
            $center = $i;
            $right = $i + $p[$i] - 1;
        }
    }

    // 找到最长回文子串的中心和长度
    $maxLen = 0;
    $centerIndex = 0;
    for ($i = 1; $i < $n - 1; $i++) {
        if ($p[$i] > $maxLen) {
            $maxLen = $p[$i];
            $centerIndex = $i;
        }
    }

    // 从预处理后的字符串中还原出原始字符串中的最长回文子串
    return substr($s, ($centerIndex - $maxLen) / 2, $maxLen - 1);
}

算法复杂度

马拉车算法的时间复杂度为O(n)，空间复杂度也为O(n)。

算法优点

  • 线性时间复杂度: 效率极高。
  • 实现相对简单: 核心思想清晰易懂。
  • 应用广泛: 在字符串处理、生物信息学等领域有广泛应用。

总结

马拉车算法是一种非常优秀的算法，它通过巧妙的预处理和利用对称性，实现了线性时间复杂度查找最长回文子串。在实际应用中，马拉车算法具有很高的效率和实用性。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/manacher-algorithm.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 马拉车算法 Manacher
赏
评 论
 上一篇
如何评判一段程序的好坏：复杂度分析
如何评判一段程序的好坏：复杂度分析
评判一段程序的好坏，除了功能的正确性之外，算法的效率也是一个非常重要的指标。而复杂度分析就是用来衡量算法效率的一种方法。 复杂度分析是什么？复杂度分析是对算法在运行过程中所需时间资源和空间资源的数量的估算。 时间复杂度: 表示算法执行时间
2024-11-21 算法
算法 复杂度分析
下一篇 
状态机：一种优雅的解决方案
状态机：一种优雅的解决方案
什么是状态机？状态机是一种数学模型，用于描述一个对象在不同状态之间的转换。在软件开发中，状态机被广泛用于表示对象的生命周期，例如订单的状态（待支付、已支付、已发货）、用户的状态（未激活、激活、禁用）等。 为什么使用状态机？ 清晰的业务逻辑：
2024-11-21 系统设计
状态机
PHP 马拉车算法 Manacher
算法
发布日期:   2024-11-21
文章字数:   790
阅读时长:   3 分

什么是马拉车算法？

马拉车算法是一种高效查找一个字符串的最长回文子串的线性时间复杂度算法。它通过巧妙的预处理和动态规划，避免了大量的重复计算，使得算法的效率得到了极大的提升。
注：回文（Palindrome）是指正读和反读都一样的字符串，即左右对称的字符串，如：level，noon，232…

算法核心思想

  • 预处理:
    • 在字符串的每个字符之间插入一个特殊字符（如#），使得原字符串变为奇数长度。这样，无论是奇数长度还是偶数长度的回文子串，都可以统一处理成奇数长度的回文子串。
  • 中心扩展:
    • 从字符串的第一个字符开始，向两边扩展，找到以当前字符为中心的回文子串的最长长度。
  • 利用对称性:
    • 算法的关键在于利用已经计算过的回文子串的信息，来加速后续回文子串的查找。通过对称性，可以减少不必要的字符比较。

算法实现步骤

  1. 预处理: 将原字符串转换为一个新的字符串，在每个字符之间插入一个特殊字符。
  2. 初始化数组P: 数组P用来存储以每个字符为中心的最长回文子串的半径。
  3. 遍历预处理后的字符串:
    • 维护一个中心id和最右边界mx。
    • 对于当前字符i，利用对称性，可以快速得到一个初始的回文半径。
    • 然后，以i为中心，向两边扩展，直到遇到不匹配的字符或者到达边界。
    • 更新P[i]，以及中心id和最右边界mx。

代码示例（php）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function longestPalindrome($s) {
    $n = strlen($s);
    $T = '#';
    for ($i = 0; $i < $n; $i++) {
        $T .= $s[$i] . '#';
    }
    $n = strlen($T);
    $p = array_fill(0, $n, 0);		// 创建数组 p，用于存储以每个位置为中心的最长回文半径。
    $center = 0;
    $right = 0;

    for ($i = 1; $i < $n - 1; $i++) {
        $mirror = 2 * $center - $i;
        $p[$i] = ($i < $right) ? min($right - $i, $p[$mirror]) : 1;

        while ($i + $p[$i] < $n && $i - $p[$i] > 0 && $T[$i + $p[$i]] == $T[$i - $p[$i]]) {
            $p[$i]++;
        }

        if ($i + $p[$i] - 1 > $right) {
            $center = $i;
            $right = $i + $p[$i] - 1;
        }
    }

    // 找到最长回文子串的中心和长度
    $maxLen = 0;
    $centerIndex = 0;
    for ($i = 1; $i < $n - 1; $i++) {
        if ($p[$i] > $maxLen) {
            $maxLen = $p[$i];
            $centerIndex = $i;
        }
    }

    // 从预处理后的字符串中还原出原始字符串中的最长回文子串
    return substr($s, ($centerIndex - $maxLen) / 2, $maxLen - 1);
}

算法复杂度

马拉车算法的时间复杂度为O(n)，空间复杂度也为O(n)。

算法优点

  • 线性时间复杂度: 效率极高。
  • 实现相对简单: 核心思想清晰易懂。
  • 应用广泛: 在字符串处理、生物信息学等领域有广泛应用。

总结

马拉车算法是一种非常优秀的算法，它通过巧妙的预处理和利用对称性，实现了线性时间复杂度查找最长回文子串。在实际应用中，马拉车算法具有很高的效率和实用性。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/manacher-algorithm.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 马拉车算法 Manacher
赏
评 论
 上一篇
如何评判一段程序的好坏：复杂度分析
如何评判一段程序的好坏：复杂度分析
评判一段程序的好坏，除了功能的正确性之外，算法的效率也是一个非常重要的指标。而复杂度分析就是用来衡量算法效率的一种方法。 复杂度分析是什么？复杂度分析是对算法在运行过程中所需时间资源和空间资源的数量的估算。 时间复杂度: 表示算法执行时间
2024-11-21 算法
算法 复杂度分析
下一篇 
状态机：一种优雅的解决方案
状态机：一种优雅的解决方案
什么是状态机？状态机是一种数学模型，用于描述一个对象在不同状态之间的转换。在软件开发中，状态机被广泛用于表示对象的生命周期，例如订单的状态（待支付、已支付、已发货）、用户的状态（未激活、激活、禁用）等。 为什么使用状态机？ 清晰的业务逻辑：
2024-11-21 系统设计
状态机
PHP 马拉车算法 Manacher
算法
发布日期:   2024-11-21
文章字数:   790
阅读时长:   3 分

什么是马拉车算法？

马拉车算法是一种高效查找一个字符串的最长回文子串的线性时间复杂度算法。它通过巧妙的预处理和动态规划，避免了大量的重复计算，使得算法的效率得到了极大的提升。
注：回文（Palindrome）是指正读和反读都一样的字符串，即左右对称的字符串，如：level，noon，232…

算法核心思想

  • 预处理:
    • 在字符串的每个字符之间插入一个特殊字符（如#），使得原字符串变为奇数长度。这样，无论是奇数长度还是偶数长度的回文子串，都可以统一处理成奇数长度的回文子串。
  • 中心扩展:
    • 从字符串的第一个字符开始，向两边扩展，找到以当前字符为中心的回文子串的最长长度。
  • 利用对称性:
    • 算法的关键在于利用已经计算过的回文子串的信息，来加速后续回文子串的查找。通过对称性，可以减少不必要的字符比较。

算法实现步骤

  1. 预处理: 将原字符串转换为一个新的字符串，在每个字符之间插入一个特殊字符。
  2. 初始化数组P: 数组P用来存储以每个字符为中心的最长回文子串的半径。
  3. 遍历预处理后的字符串:
    • 维护一个中心id和最右边界mx。
    • 对于当前字符i，利用对称性，可以快速得到一个初始的回文半径。
    • 然后，以i为中心，向两边扩展，直到遇到不匹配的字符或者到达边界。
    • 更新P[i]，以及中心id和最右边界mx。

代码示例（php）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function longestPalindrome($s) {
    $n = strlen($s);
    $T = '#';
    for ($i = 0; $i < $n; $i++) {
        $T .= $s[$i] . '#';
    }
    $n = strlen($T);
    $p = array_fill(0, $n, 0);		// 创建数组 p，用于存储以每个位置为中心的最长回文半径。
    $center = 0;
    $right = 0;

    for ($i = 1; $i < $n - 1; $i++) {
        $mirror = 2 * $center - $i;
        $p[$i] = ($i < $right) ? min($right - $i, $p[$mirror]) : 1;

        while ($i + $p[$i] < $n && $i - $p[$i] > 0 && $T[$i + $p[$i]] == $T[$i - $p[$i]]) {
            $p[$i]++;
        }

        if ($i + $p[$i] - 1 > $right) {
            $center = $i;
            $right = $i + $p[$i] - 1;
        }
    }

    // 找到最长回文子串的中心和长度
    $maxLen = 0;
    $centerIndex = 0;
    for ($i = 1; $i < $n - 1; $i++) {
        if ($p[$i] > $maxLen) {
            $maxLen = $p[$i];
            $centerIndex = $i;
        }
    }

    // 从预处理后的字符串中还原出原始字符串中的最长回文子串
    return substr($s, ($centerIndex - $maxLen) / 2, $maxLen - 1);
}

算法复杂度

马拉车算法的时间复杂度为O(n)，空间复杂度也为O(n)。

算法优点

  • 线性时间复杂度: 效率极高。
  • 实现相对简单: 核心思想清晰易懂。
  • 应用广泛: 在字符串处理、生物信息学等领域有广泛应用。

总结

马拉车算法是一种非常优秀的算法，它通过巧妙的预处理和利用对称性，实现了线性时间复杂度查找最长回文子串。在实际应用中，马拉车算法具有很高的效率和实用性。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/manacher-algorithm.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 马拉车算法 Manacher
赏
评 论
 上一篇
如何评判一段程序的好坏：复杂度分析
如何评判一段程序的好坏：复杂度分析
评判一段程序的好坏，除了功能的正确性之外，算法的效率也是一个非常重要的指标。而复杂度分析就是用来衡量算法效率的一种方法。 复杂度分析是什么？复杂度分析是对算法在运行过程中所需时间资源和空间资源的数量的估算。 时间复杂度: 表示算法执行时间
2024-11-21 算法
算法 复杂度分析
下一篇 
状态机：一种优雅的解决方案
状态机：一种优雅的解决方案
什么是状态机？状态机是一种数学模型，用于描述一个对象在不同状态之间的转换。在软件开发中，状态机被广泛用于表示对象的生命周期，例如订单的状态（待支付、已支付、已发货）、用户的状态（未激活、激活、禁用）等。 为什么使用状态机？ 清晰的业务逻辑：
2024-11-21 系统设计
状态机
  目录
  目录
  目录
hexo