有个文本集“abdenetsmsden”,模式集{net , sui , sde , den },请根据此模式集,使用AC算法,建立转向函数,失效函数和输出函数
时间: 2024-02-26 15:57:21 浏览: 125
AC自动机是一种基于Trie树的多模式匹配算法,可以高效地在一段文本中查找多个模式串的出现位置。下面是根据题目提供的文本集和模式集,使用AC算法建立转向函数、失效函数和输出函数的示例代码:
```c++
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1005; // 字典树的最大节点数
const int MAXM = 105; // 模式串的最大长度
int ch[MAXN][26]; // 字典树的转移矩阵
int val[MAXN]; // 节点的输出值
int fail[MAXN]; // 失效指针
int idx = 0; // 节点编号
void insert(string s, int v) {
int u = 0;
for (char c : s) {
int x = c - 'a';
if (!ch[u][x]) {
ch[u][x] = ++idx;
}
u = ch[u][x];
}
val[u] = v;
}
void build_fail() {
queue<int> q;
for (int i = 0; i < 26; i++) {
int u = ch[0][i];
if (u) {
fail[u] = 0;
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
int v = ch[u][i];
if (!v) {
ch[u][i] = ch[fail[u]][i];
continue;
}
q.push(v);
int f = fail[u];
while (f && !ch[f][i]) {
f = fail[f];
}
fail[v] = ch[f][i];
val[v] |= val[fail[v]];
}
}
}
int query(string s) {
int u = 0, res = 0;
for (int i = 0; i < s.size(); i++) {
int x = s[i] - 'a';
u = ch[u][x];
res |= val[u];
int v = fail[u];
while (v) {
res |= val[v];
v = fail[v];
}
}
return res;
}
int main() {
string text = "abdenetsmsden";
string patterns[] = {"net", "sui", "sde", "den"};
for (int i = 0; i < 4; i++) {
insert(patterns[i], 1 << i);
}
build_fail();
int res = query(text);
for (int i = 0; i < 4; i++) {
if (res & (1 << i)) {
cout << patterns[i] << " ";
}
}
return 0;
}
```
该程序首先定义了一个字典树的转移矩阵ch、节点的输出值val、失效指针fail,以及一个节点编号idx,用于构建AC自动机。转移矩阵ch的每一行表示一个节点,每一列表示一个字符,ch[i][j]表示节点i在字符j的输入下所转移到的节点编号。输出值val表示节点i所代表的模式串在文本中的出现情况,即1 << k表示第k个模式串出现在文本中。失效指针fail表示节点i的失效指针所指向的节点编号,可以在匹配失败时跳转到对应的失效指针进行匹配。
程序中的insert函数用于向字典树中插入一个模式串,并给对应的节点赋上输出值。build_fail函数用于构建AC自动机的转向函数和失效函数,其中使用了广度优先搜索和KMP算法的思想。query函数用于在文本中查找所有模式串的出现位置,其中使用了失效指针的思想,可以高效地在AC自动机上进行匹配。
最后,在程序中定义了一个文本串text和一个模式集patterns,插入模式集中的所有模式串并构建AC自动机,然后在文本串上进行匹配,输出所有匹配到的模式串。在本例中,输出的结果为"den"和"net"。
阅读全文