有文本集“All_of_the_students_are_very_cool_in_this_school.”,模式集{student , crude , school},请根据此模式集,使用c++,使用Wu-Manber算法,假设B = 2,计算SHIFT表、HASH表和PREFIX表。
时间: 2024-02-25 14:58:32 浏览: 20
好的,这里提供一个简单的C++实现,使用Wu-Manber算法,计算SHIFT表、HASH表和PREFIX表。假设B = 2,模式集{student , crude , school},文本集“All_of_the_students_are_very_cool_in_this_school.”:
```
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100005, P = 131; // N为文本串长度上限,P为哈希素数
int n; // 模式串的个数
char text[N]; // 文本串
char pattern[105][105]; // 模式串集合
int m[105]; // 模式串的长度
int B = 2; // B为分块大小
int shift[105][1 << B]; // SHIFT表
int hash[105][1 << B]; // HASH表
int prefix[105][1 << B]; // PREFIX表
void init() // 初始化
{
memset(shift, 0, sizeof shift);
memset(hash, 0, sizeof hash);
memset(prefix, 0, sizeof prefix);
}
int get_hash(char str[], int len) // 计算哈希值
{
int h = 0;
for (int i = 0; i < len; i++)
h = h * P + str[i];
return h;
}
int count_one(int x) // 统计二进制数中1的个数
{
int res = 0;
while (x)
{
x &= (x - 1);
res++;
}
return res;
}
void build_shift_table() // 建立SHIFT表
{
for (int i = 0; i < n; i++)
{
int len = m[i];
for (int j = 0; j < len - B + 1; j++)
{
int k = j / B, l = j % B;
shift[i][k] |= (1 << l);
}
}
}
void build_hash_table() // 建立HASH表
{
for (int i = 0; i < n; i++)
{
int len = m[i];
for (int j = 0; j < len - B + 1; j++)
{
int k = j / B, l = j % B;
hash[i][k] = (hash[i][k] << B) + (int)pattern[i][j + B - 1];
}
}
}
void build_prefix_table() // 建立PREFIX表
{
for (int i = 0; i < n; i++)
{
int len = m[i];
for (int j = 0; j < len - B + 1; j++)
{
int k = j / B, l = j % B;
if (l == 0) prefix[i][k] = (1 << B) - 1;
else prefix[i][k] |= (1 << (l - 1));
}
}
}
void match() // 匹配文本串
{
int len = strlen(text);
for (int i = 0; i < len - B + 1; i++)
{
int j = 0, k = i / B, l = i % B, t = 0;
while (j < n && t <= B)
{
if ((shift[j][k] & (1 << l)) && (hash[j][k] == get_hash(text + i - t, t + B)))
{
int cnt = count_one(prefix[j][k] & ((1 << l) - 1));
if (t + cnt >= m[j])
{
cout << "match pattern " << pattern[j] << " at position " << i - m[j] + 1 << endl;
break;
}
}
j++;
t++;
}
}
}
int main()
{
init();
strcpy(text, "All_of_the_students_are_very_cool_in_this_school.");
n = 3;
strcpy(pattern[0], "student");
strcpy(pattern[1], "crude");
strcpy(pattern[2], "school");
m[0] = strlen(pattern[0]);
m[1] = strlen(pattern[1]);
m[2] = strlen(pattern[2]);
build_shift_table();
build_hash_table();
build_prefix_table();
match();
return 0;
}
```
其中,SHIFT表、HASH表和PREFIX表的建立过程分别在build_shift_table()、build_hash_table()和build_prefix_table()函数中实现,匹配文本串的过程在match()函数中实现。在代码中,B表示分块大小,get_hash()函数用于计算哈希值,count_one()函数用于统计二进制数中1的个数。最后输出匹配模式串的位置。