C++ Boyer Moore 模式搜索算法

模式识别是计算机科学领域中的一个重要问题。当我们在记事本/Word文档、浏览器或数据库中搜索字符串时，模式搜索方法会显示搜索结果。下面是一个问题描述的示例：

给定一个字符串 text[0..n-1] 和一个模式 pattern[0..m-1]，编写一个函数search(char pattern[], char text[])，输出text[]中pattern[]的所有实例。您可以假设n > m。在我们深入探讨如何搜索或识别字符串中给定模式的出现之前，让我们首先回顾一下什么是字符串。

字符串表示一种不可变数据类型，用于存储字符序列。字符串是任何计算机语言中最常用的数据类型。使用引号（单引号或双引号）可以轻松创建字符串。

我们现在可以应用Boyer Moore模式搜索方法（或B-M算法）来在字符串中查找模式。Boyer-Moore算法的概念很简单：两个指针分别对齐文本字符串和相应字符字符串的第0个位置。如果字符不同，Boyer-Moore算法会以两种方式同时移动字符。所以，我们可以说Boyer-Moore算法是两种技术的混合：

1. 坏字符启发式
2. 好后缀启发式。

方法1：坏字符启发式

如果找到匹配，则返回模式的起始索引。否则，有两种可能性：

当模式包含与输入文本中不匹配的字符时

在这种情况下，该字符被称为坏字符。当识别出坏字符时，我们将移动模式，直到它与不匹配的文本字符匹配。

考虑模式字符串和输入文本不直接匹配的情况。假设模式字符串是"WORLD"，输入文本是"HELLOHELLO"。我们将使用Boyer-Moore字符串搜索技术来查找与输入文本匹配的模式。

示例

模式：WORLD

字符串：HELLOHELLO

现在，让我们使用Boyer-Moore技术将模式与输入文本进行比较：

步骤1：检查最后两个字符，D 和 O。它们不兼容。

在此示例中，输入文本中模式内没有不匹配的字符。使用坏字符规则，计算机会更改模式以与不匹配的字符对应。

移位后

模式：WORLD

输入文本：HELLOHELLO

步骤2：匹配最后两个字符，D 和 L。它们不兼容。

按长度更改模式并再次运行坏字符条件。

移位后

模式：WORLD

输入文本：HELLOHELLO

此过程重复，直到模式针对整个输入文本进行测试，并且没有找到匹配，表明无法找到识别的模式。在此示例中，模式"WORLD"与输入字符串"HELLOHELLO"不对应。

文件名：PattrernMatch.cpp

输出

The pattern present at the position = 5

方法2：好后缀启发式。

让我们看一个输入字符串"HelloWorld"，模式为"WORLD"，以演示Boyer-Moore方法如何使用好后缀启发式。

模式：WORLD

输入：HELLOWORLD

现在，将使用好后缀启发式方法将模式与输入文本进行比较：

• 比较最后两个字符，D 和 D。
• 通过向左移动，比较接下来的两个字符，L 和 L。
• 继续进行，直到模式中的所有字符都匹配。
• 最后，我们发现输入字符串"HELLOWORLD"中从索引5开始有一个匹配，因为模式中的每个字符都与文本中的字符对应。

文件名：PatternMatch2.cpp

输出

The pattern found at position = 0
The pattern found at position = 10