C++ 程序实现字符串匹配的 Bitap 算法
c++server side programmingprogramming
这是一个 C++ 程序实现字符串匹配的 Bitap 算法。该算法判断给定文本是否包含与给定模式"近似相等"的子字符串，其中近似相等是根据 Levenshtein 距离定义的 - 如果子字符串和模式在给定距离 k 内，则根据算法，它们是相等的。它首先预先计算一组位掩码，其中包含模式每个元素的一个位。因此，我们能够使用速度极快的按位运算完成大部分工作。
算法
开始 将字符串和模式作为输入。 函数 bitmap_search() 接受参数字符串文本 t 和字符串模式 p : 初始化位数组 A。 初始化模式位掩码，p_mask[300] 更新位数组。 对于 i = 0 到 299 p_mask[i] = ~0 对于 i = 0 到 m-1 p_mask[p[i]] and= ~(1L 左移 i); 对于 i = 0 到 t.length()-1 A |= p_mask[t[i]]; A <<= 1; 如果 ((A and (1L 左移 m)) == 0 返回 i - m + 1 返回 -1 结束
示例代码
#include <string>
#include <map>
#include <iostream>
using namespace std;
int bitmap_search(string t, string p) {
int m = p.length();
long p_mask[300];
long A = ~1;
if (m == 0)
return -1;
if (m >63) {
cout<<"模式太长!";//如果模式太长
return -1;
}
for (int i = 0; i <= 299; ++i)
p_mask[i] = ~0;
for (int i = 0; i < m; ++i)
p_mask[p[i]] &= ~(1L << i);
for (int i = 0; i < t.length(); ++i) {
A |= p_mask[t[i]];
A <<= 1;
if ((A & (1L << m)) == 0)
return i - m + 1;
}
return -1;
}
void findPattern(string t, string p) {
int position = bitmap_search(t, p);//使用函数 bitmap_search 初始化位置
if (position == -1)
cout << "\nNo Match\n";
else
cout << "\nPattern found at position : " << position;
}
int main(int argc, char **argv) {
cout << "Enter Text:\n";
string t;
cin >>t;
cout << "Enter Pattern:\n";
string p;
cin >>p;
findPattern(t, p);
}
输出
Enter Text: Tutorialspoint Enter Pattern: point Pattern found at position : 9
