有个文本集“abdenetsmsden”,模式集{net , sui , sde , den },请根据此模式集,使用c++,使用AC算法,建立转向函数,失效函数和输出函数
时间: 2024-02-25 15:58:30 浏览: 59
图像显著性检测数据集SDE2、PASCAL-S百度云分享
好的,这里提供一个简单的C++实现,使用AC自动机算法,建立转移函数、失效函数和输出函数:
```
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100005, M = 26; // N为Trie树节点数,M为字符集大小
int n; // 模式串的个数
char text[N]; // 文本串
char pattern[105][105]; // 模式串集合
int trie[N][M], idx; // Trie树数组,idx表示节点编号
int fail[N]; // 失效指针数组
int vis[N]; // 标记数组,用于防止多次匹配
int cnt[105]; // 记录每个模式串出现的次数
void insert(char str[]) // 插入一个模式串
{
int p = 0;
for (int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if (!trie[p][u]) trie[p][u] = ++idx;
p = trie[p][u];
}
cnt[n] = 0; // 初始化计数器
}
void build() // 建立AC自动机
{
queue<int> q;
for (int i = 0; i < M; i++)
{
int u = trie[0][i];
if (u) q.push(u);
}
while (q.size())
{
int p = q.front(); q.pop();
for (int i = 0; i < M; i++)
{
int u = trie[p][i];
if (!u) trie[p][i] = trie[fail[p]][i];
else
{
fail[u] = trie[fail[p]][i];
q.push(u);
}
}
}
}
void match(char str[]) // 匹配文本串
{
memset(vis, 0, sizeof vis);
int p = 0;
for (int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
p = trie[p][u];
for (int j = p; j; j = fail[j])
{
if (vis[j]) continue; // 防止重复匹配
vis[j] = true;
cnt[j]++; // 计数器加1
}
}
}
int main()
{
scanf("%s", text);
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", pattern[i]);
insert(pattern[i]);
}
build();
match(text);
for (int i = 0; i < n; i++)
printf("%d\n", cnt[i]);
return 0;
}
```
其中,建立转移函数和失效函数的过程在build()函数中实现,匹配文本串的过程在match()函数中实现,输出每个模式串出现的次数在最后的for循环中实现。这段代码中,idx表示Trie树的节点编号,fail表示失效指针,vis表示标记数组,cnt表示计数器,用于记录每个模式串出现的次数。
阅读全文