喜迎
春节

Boyer-Moore算法

PHP 算法 Boyer-Moore
算法
发布日期:   2024-11-21
文章字数:   892
阅读时长:   3 分

Boyer-Moore算法简介

Boyer-Moore算法是一种高效的字符串搜索算法，它通过跳过文本中明显不匹配的部分，显著提高了搜索效率。相较于传统的暴力匹配算法，Boyer-Moore算法在大多数情况下性能更佳，尤其是在搜索较长的模式串时。

算法的核心思想：

  • 坏字符规则： 当模式串的一个字符与文本中的字符不匹配时，模式串向右滑动，使得不匹配的字符与文本中对应的字符对齐。
  • 好后缀规则： 当模式串的后缀与文本中的部分匹配时，模式串向右滑动，使得匹配的后缀与文本中对应的后缀对齐。

算法实现步骤

  1. 构建坏字符表:
    • 对于模式串中的每个字符，记录它在模式串中最后出现的位置。
    • 如果字符不在模式串中出现，则其位置为模式串的长度。
  2. 构建好后缀表:
    • 计算模式串的后缀与自身匹配的最长长度。
  3. 搜索过程:
    • 从模式串的末尾开始与文本进行比较。
    • 如果不匹配，则根据坏字符规则或好后缀规则计算滑动距离，将模式串向右滑动。
    • 重复步骤3，直到找到匹配或到达文本末尾。

PHP实现Boyer-Moore算法

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
39
40
41
42
43
function boyerMooreSearch($text, $pattern) {
    $m = strlen($pattern);
    $n = strlen($text);
    $badChar = [];
    $goodSuffix = [];

    // 初始化坏字符表
    for ($i = 0; $i < 256; $i++) {
        $badChar[$i] = $m;
    }
    for ($i = 0; $i < $m - 1; $i++) {
        $badChar[ord($pattern[$i])] = $m - $i - 1;
    }

    // 初始化好后缀表（简化版）
    // 这里使用一个简单的实现，实际应用中可以优化
    for ($i = 0; $i < $m; $i++) {
        $goodSuffix[$i] = $m;
    }
    for ($i = $m - 2; $i >= 0; $i--) {
        $j = $i;
        while ($j >= 0 && $pattern[$j] === $pattern[$m - 1 - $i + $j]) {
            $goodSuffix[$j] = $i + 1;
            $j--;
        }
    }

    $i = 0;
    while ($i <= $n - $m) {
        $j = $m - 1;
        while ($j >= 0 && $pattern[$j] === $text[$i + $j]) {
            $j--;
        }

        if ($j < 0) {
            return $i; // 匹配成功
        } else {
            $i += max($badChar[ord($text[$i + $j])] - $m + 1 + $j, $goodSuffix[$j]);
        }
    }

    return -1; // 未找到匹配
}
  • 代码解释
  1. 坏字符表: 记录每个字符在模式串中最后出现的位置。
  2. 好后缀表: 记录模式串的后缀与自身匹配的最长长度。
  3. 匹配过程: 从模式串末尾开始与文本比较，若不匹配，则根据坏字符规则或好后缀规则计算滑动距离。

算法优化

  • 坏字符表优化: 可以使用更复杂的算法来计算坏字符表，以提高算法效率。
  • 好后缀表优化: 可以使用KMP算法的思想来计算好后缀表。
  • 多模式匹配: 可以将Boyer-Moore算法扩展为多模式匹配算法。

算法应用场景

  • 文本搜索: 在大文本中快速查找子串。
  • 字符串匹配: 在生物信息学、信息检索等领域有广泛应用。
  • 数据压缩: 在压缩算法中用于查找重复模式。

算法优点

  • 效率高: 通过跳过不匹配的部分，大大提高了搜索速度。
  • 适用于长模式串: 尤其在搜索较长的模式串时，性能优势更加明显。

算法缺点

  • 实现复杂: 算法的实现相对复杂，特别是好后缀表的计算。

总结

Boyer-Moore算法是一种高效的字符串搜索算法，通过巧妙的跳跃机制，可以显著提高搜索效率。PHP实现相对简单，但要深入理解算法的原理才能进行优化和扩展。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/boyer-moore.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Boyer-Moore
赏
评 论
 上一篇
如何隐蔽地对白嫖用户设置更严格的活动限制
如何隐蔽地对白嫖用户设置更严格的活动限制
在游戏中，策划为了鼓励用户付费，往往会对白嫖用户设置一些限制，这在业内是比较常见的做法。然而，过于明显的限制会引起玩家的反感，导致玩家流失。因此，如何将这些限制设置得更加隐蔽，就成为了策划需要考虑的问题。 隐蔽设置限制的思路与方法 概率性限
2024-11-21 游戏设计
design 白嫖
下一篇 
Luhn算法详解
Luhn算法详解
Luhn算法，也称为模10算法，是一种简单的校验和算法，常用于验证各种身份识别码，比如银行卡号、国际移动设备识别码（IMEI）、美国国家提供商标识号码等。它能快速地检测出输入中的单一数字错误，例如错位、漏掉或多输入一个数字。 Luhn算法的
2024-11-21 算法
PHP Luhn算法
PHP 算法 Boyer-Moore
算法
发布日期:   2024-11-21
文章字数:   892
阅读时长:   3 分

Boyer-Moore算法简介

Boyer-Moore算法是一种高效的字符串搜索算法，它通过跳过文本中明显不匹配的部分，显著提高了搜索效率。相较于传统的暴力匹配算法，Boyer-Moore算法在大多数情况下性能更佳，尤其是在搜索较长的模式串时。

算法的核心思想：

  • 坏字符规则： 当模式串的一个字符与文本中的字符不匹配时，模式串向右滑动，使得不匹配的字符与文本中对应的字符对齐。
  • 好后缀规则： 当模式串的后缀与文本中的部分匹配时，模式串向右滑动，使得匹配的后缀与文本中对应的后缀对齐。

算法实现步骤

  1. 构建坏字符表:
    • 对于模式串中的每个字符，记录它在模式串中最后出现的位置。
    • 如果字符不在模式串中出现，则其位置为模式串的长度。
  2. 构建好后缀表:
    • 计算模式串的后缀与自身匹配的最长长度。
  3. 搜索过程:
    • 从模式串的末尾开始与文本进行比较。
    • 如果不匹配，则根据坏字符规则或好后缀规则计算滑动距离，将模式串向右滑动。
    • 重复步骤3，直到找到匹配或到达文本末尾。

PHP实现Boyer-Moore算法

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
39
40
41
42
43
function boyerMooreSearch($text, $pattern) {
    $m = strlen($pattern);
    $n = strlen($text);
    $badChar = [];
    $goodSuffix = [];

    // 初始化坏字符表
    for ($i = 0; $i < 256; $i++) {
        $badChar[$i] = $m;
    }
    for ($i = 0; $i < $m - 1; $i++) {
        $badChar[ord($pattern[$i])] = $m - $i - 1;
    }

    // 初始化好后缀表（简化版）
    // 这里使用一个简单的实现，实际应用中可以优化
    for ($i = 0; $i < $m; $i++) {
        $goodSuffix[$i] = $m;
    }
    for ($i = $m - 2; $i >= 0; $i--) {
        $j = $i;
        while ($j >= 0 && $pattern[$j] === $pattern[$m - 1 - $i + $j]) {
            $goodSuffix[$j] = $i + 1;
            $j--;
        }
    }

    $i = 0;
    while ($i <= $n - $m) {
        $j = $m - 1;
        while ($j >= 0 && $pattern[$j] === $text[$i + $j]) {
            $j--;
        }

        if ($j < 0) {
            return $i; // 匹配成功
        } else {
            $i += max($badChar[ord($text[$i + $j])] - $m + 1 + $j, $goodSuffix[$j]);
        }
    }

    return -1; // 未找到匹配
}
  • 代码解释
  1. 坏字符表: 记录每个字符在模式串中最后出现的位置。
  2. 好后缀表: 记录模式串的后缀与自身匹配的最长长度。
  3. 匹配过程: 从模式串末尾开始与文本比较，若不匹配，则根据坏字符规则或好后缀规则计算滑动距离。

算法优化

  • 坏字符表优化: 可以使用更复杂的算法来计算坏字符表，以提高算法效率。
  • 好后缀表优化: 可以使用KMP算法的思想来计算好后缀表。
  • 多模式匹配: 可以将Boyer-Moore算法扩展为多模式匹配算法。

算法应用场景

  • 文本搜索: 在大文本中快速查找子串。
  • 字符串匹配: 在生物信息学、信息检索等领域有广泛应用。
  • 数据压缩: 在压缩算法中用于查找重复模式。

算法优点

  • 效率高: 通过跳过不匹配的部分，大大提高了搜索速度。
  • 适用于长模式串: 尤其在搜索较长的模式串时，性能优势更加明显。

算法缺点

  • 实现复杂: 算法的实现相对复杂，特别是好后缀表的计算。

总结

Boyer-Moore算法是一种高效的字符串搜索算法，通过巧妙的跳跃机制，可以显著提高搜索效率。PHP实现相对简单，但要深入理解算法的原理才能进行优化和扩展。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/boyer-moore.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Boyer-Moore
赏
评 论
 上一篇
如何隐蔽地对白嫖用户设置更严格的活动限制
如何隐蔽地对白嫖用户设置更严格的活动限制
在游戏中，策划为了鼓励用户付费，往往会对白嫖用户设置一些限制，这在业内是比较常见的做法。然而，过于明显的限制会引起玩家的反感，导致玩家流失。因此，如何将这些限制设置得更加隐蔽，就成为了策划需要考虑的问题。 隐蔽设置限制的思路与方法 概率性限
2024-11-21 游戏设计
design 白嫖
下一篇 
Luhn算法详解
Luhn算法详解
Luhn算法，也称为模10算法，是一种简单的校验和算法，常用于验证各种身份识别码，比如银行卡号、国际移动设备识别码（IMEI）、美国国家提供商标识号码等。它能快速地检测出输入中的单一数字错误，例如错位、漏掉或多输入一个数字。 Luhn算法的
2024-11-21 算法
PHP Luhn算法
PHP 算法 Boyer-Moore
算法
发布日期:   2024-11-21
文章字数:   892
阅读时长:   3 分

Boyer-Moore算法简介

Boyer-Moore算法是一种高效的字符串搜索算法，它通过跳过文本中明显不匹配的部分，显著提高了搜索效率。相较于传统的暴力匹配算法，Boyer-Moore算法在大多数情况下性能更佳，尤其是在搜索较长的模式串时。

算法的核心思想：

  • 坏字符规则： 当模式串的一个字符与文本中的字符不匹配时，模式串向右滑动，使得不匹配的字符与文本中对应的字符对齐。
  • 好后缀规则： 当模式串的后缀与文本中的部分匹配时，模式串向右滑动，使得匹配的后缀与文本中对应的后缀对齐。

算法实现步骤

  1. 构建坏字符表:
    • 对于模式串中的每个字符，记录它在模式串中最后出现的位置。
    • 如果字符不在模式串中出现，则其位置为模式串的长度。
  2. 构建好后缀表:
    • 计算模式串的后缀与自身匹配的最长长度。
  3. 搜索过程:
    • 从模式串的末尾开始与文本进行比较。
    • 如果不匹配，则根据坏字符规则或好后缀规则计算滑动距离，将模式串向右滑动。
    • 重复步骤3，直到找到匹配或到达文本末尾。

PHP实现Boyer-Moore算法

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
39
40
41
42
43
function boyerMooreSearch($text, $pattern) {
    $m = strlen($pattern);
    $n = strlen($text);
    $badChar = [];
    $goodSuffix = [];

    // 初始化坏字符表
    for ($i = 0; $i < 256; $i++) {
        $badChar[$i] = $m;
    }
    for ($i = 0; $i < $m - 1; $i++) {
        $badChar[ord($pattern[$i])] = $m - $i - 1;
    }

    // 初始化好后缀表（简化版）
    // 这里使用一个简单的实现，实际应用中可以优化
    for ($i = 0; $i < $m; $i++) {
        $goodSuffix[$i] = $m;
    }
    for ($i = $m - 2; $i >= 0; $i--) {
        $j = $i;
        while ($j >= 0 && $pattern[$j] === $pattern[$m - 1 - $i + $j]) {
            $goodSuffix[$j] = $i + 1;
            $j--;
        }
    }

    $i = 0;
    while ($i <= $n - $m) {
        $j = $m - 1;
        while ($j >= 0 && $pattern[$j] === $text[$i + $j]) {
            $j--;
        }

        if ($j < 0) {
            return $i; // 匹配成功
        } else {
            $i += max($badChar[ord($text[$i + $j])] - $m + 1 + $j, $goodSuffix[$j]);
        }
    }

    return -1; // 未找到匹配
}
  • 代码解释
  1. 坏字符表: 记录每个字符在模式串中最后出现的位置。
  2. 好后缀表: 记录模式串的后缀与自身匹配的最长长度。
  3. 匹配过程: 从模式串末尾开始与文本比较，若不匹配，则根据坏字符规则或好后缀规则计算滑动距离。

算法优化

  • 坏字符表优化: 可以使用更复杂的算法来计算坏字符表，以提高算法效率。
  • 好后缀表优化: 可以使用KMP算法的思想来计算好后缀表。
  • 多模式匹配: 可以将Boyer-Moore算法扩展为多模式匹配算法。

算法应用场景

  • 文本搜索: 在大文本中快速查找子串。
  • 字符串匹配: 在生物信息学、信息检索等领域有广泛应用。
  • 数据压缩: 在压缩算法中用于查找重复模式。

算法优点

  • 效率高: 通过跳过不匹配的部分，大大提高了搜索速度。
  • 适用于长模式串: 尤其在搜索较长的模式串时，性能优势更加明显。

算法缺点

  • 实现复杂: 算法的实现相对复杂，特别是好后缀表的计算。

总结

Boyer-Moore算法是一种高效的字符串搜索算法，通过巧妙的跳跃机制，可以显著提高搜索效率。PHP实现相对简单，但要深入理解算法的原理才能进行优化和扩展。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/boyer-moore.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Boyer-Moore
赏
评 论
 上一篇
如何隐蔽地对白嫖用户设置更严格的活动限制
如何隐蔽地对白嫖用户设置更严格的活动限制
在游戏中，策划为了鼓励用户付费，往往会对白嫖用户设置一些限制，这在业内是比较常见的做法。然而，过于明显的限制会引起玩家的反感，导致玩家流失。因此，如何将这些限制设置得更加隐蔽，就成为了策划需要考虑的问题。 隐蔽设置限制的思路与方法 概率性限
2024-11-21 游戏设计
design 白嫖
下一篇 
Luhn算法详解
Luhn算法详解
Luhn算法，也称为模10算法，是一种简单的校验和算法，常用于验证各种身份识别码，比如银行卡号、国际移动设备识别码（IMEI）、美国国家提供商标识号码等。它能快速地检测出输入中的单一数字错误，例如错位、漏掉或多输入一个数字。 Luhn算法的
2024-11-21 算法
PHP Luhn算法
  目录
  目录
  目录
hexo