資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律專業C++ 程式實現用於字串匹配的 Bitap 演算法
本篇為 C++ 程式，介紹瞭如何實現用於字串匹配的 Bitap 演算法。該演算法判斷給定的文字是否包含與給定模式“近似相等”的子字串，其中近似相等由 Levenshtein 距離定義——如果子字串與模式之間的距離小於給定距離 k，則根據該演算法，二者是相等的。該演算法首先為模式的每個元素預先計算一組包含一個位的位掩碼。這樣，我們可以利用位運算完成大部分工作。位運算的速度極其快。
演算法
Begin Take the string and pattern as input. function bitmap_search() and it takes argument string text t and string pattern p : Initialize the bit array A. Initialize the pattern bitmasks, p_mask[300] Update the bit array. for i = 0 to 299 p_mask[i] = ~0 for i = 0 to m-1 p_mask[p[i]] and= ~(1L left shift i); for i = 0 to t.length()-1 A |= p_mask[t[i]]; A <<= 1; if ((A and (1L left shift m)) == 0 return i - m + 1 return -1 End
示例程式碼
#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<<"Pattern is too long!";//if pattern is too long
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);//initialize the position with the function 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
更新時間：30-Jul-2019
371 次瀏覽
廣告