C++ 程序实现 Bitap 字符串匹配算法

Bitap 算法，又称 Shift-Or 算法，是一种字符串搜索算法，可以高效地执行近似字符串匹配。它在模式中可能存在错误或变体时查找文本中的模式特别有用。Bitap 算法由 John Colquhoun 和 Gaston Gonnet 于 1980 年提出。

示例

让我们来看看一个实现 Bitap 算法进行字符串匹配的 C++ 程序。

输出

说明

该程序实现了 Bitap 算法进行字符串匹配。程序中存在的变量是 't'，表示输入文本，'p' 是输入模式，'m' 表示模式的长度，'p_mask' 表示模式中每个字符的位掩码数组，'A' 是用于位操作的变量，'position' 表示在文本中找到模式的位置。

函数 'bitmap_search' 接受字符串 't' 和模式 'p'，并返回模式在文本中的位置，如果未找到则返回 -1。该函数使用位操作在文本中搜索模式。它为模式中的字符创建位掩码，然后执行位操作以识别模式在文本中的位置。另一个名为 find pattern 的函数接受字符串 't' 作为输入文本，字符串 'p' 作为模式，并显示模式是否找到及其位置。此函数调用 bitmap_search 函数并打印结果。如果找到模式，它会显示位置，否则打印 'No Match'。

主函数接受两个字符串，分别表示用户的输入字符串和模式。之后，调用 findpattern 函数搜索模式并显示结果。

示例 2

让我们来看看另一种在 C++ 中实现 Bitap 算法进行字符串匹配的方法。

输出

说明

该程序实现了 Bitap 算法进行字符串匹配。它高效地在文本中搜索模式，提供近似字符串匹配功能。该程序有一个 Bitap 类，其中包含一个接受模式并计算其长度的构造函数。类中存在的函数是 Preprocess 函数和 Search 函数。Preprocess 函数为模式中的每个字符创建位掩码，存储在 textMasks_vector 中。Search 函数使用位操作在文本中查找模式并打印找到模式的位置。主函数从用户那里获取文本和模式的输入，并显示在文本中找到模式的位置。此主函数将使用提供的模式创建 Bitmap 类的实例或对象，要求用户输入，并调用 Bitap 类的 Search 函数来查找并打印在文本中找到模式的位置。