AC自动机(模板)
发布日期:2021-11-02 09:48:41
浏览次数:3
分类:技术文章
本文共 4596 字,大约阅读时间需要 15 分钟。
AC自动机
用于解决多模式串匹配
#includeusing namespace std;const int maxn = 1e5 + 7;struct Trie { int next[maxn][26], fail[maxn], end[maxn]; int root, L; int newnode() { for (int i = 0; i < 26; i++) next[L][i] = -1; end[L++] = 0; return L - 1; } void init() { L = 0; root = newnode(); } void insert(char *buf) { int len = strlen(buf); int now = root; for (int i = 0; i < len; i++) { if (next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode(); now = next[now][buf[i] - 'a']; } end[now]++; } void build() { queue Q; fail[root] = root; for (int i = 0; i < 26; i++) if (next[root][i] == -1) next[root][i] = root; else { fail[next[root][i]] = root; Q.push(next[root][i]); } while (!Q.empty()) { int now = Q.front(); Q.pop(); for (int i = 0; i < 26; i++) if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { fail[next[now][i]] = next[fail[now]][i]; Q.push(next[now][i]); } } } int query(string buf) { int len = buf.length(); int now = root; int res = 0; for (int i = 0; i < len; i++) { now = next[now][buf[i] - 'a']; int temp = now; while (temp != root) { res += end[temp]; end[temp] = 0; temp = fail[temp]; } } return res; } void debug() { for (int i = 0; i < L; i++) { printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], end[i]); for (int j = 0; j < 26; j++) printf("%2d", next[i][j]); printf("]\n"); } }};char str[maxn];Trie ac;string pat;
例题:HDU 2222
第一行输入测试数据的组数,然后输入一个整数n,接下来的n行每行输入一个单词,最后输入一个字符串,问在这个字符串中有多少个单词出现过。
求目标串中出现了几个模式串
#includeusing namespace std;const int maxn = 1e5 + 7;struct Trie { int next[maxn][26], fail[maxn], end[maxn]; int root, L; int newnode() { for (int i = 0; i < 26; i++) next[L][i] = -1; end[L++] = 0; return L - 1; } void init() { L = 0; root = newnode(); } void insert(char *buf) { int len = strlen(buf); int now = root; for (int i = 0; i < len; i++) { if (next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode(); now = next[now][buf[i] - 'a']; } end[now]++; } void build() { queue Q; fail[root] = root; for (int i = 0; i < 26; i++) if (next[root][i] == -1) next[root][i] = root; else { fail[next[root][i]] = root; Q.push(next[root][i]); } while (!Q.empty()) { int now = Q.front(); Q.pop(); for (int i = 0; i < 26; i++) if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { fail[next[now][i]] = next[fail[now]][i]; Q.push(next[now][i]); } } } int query(string buf) { int len = buf.length(); int now = root; int res = 0; for (int i = 0; i < len; i++) { now = next[now][buf[i] - 'a']; int temp = now; while (temp != root) { res += end[temp]; end[temp] = 0; temp = fail[temp]; } } return res; } void debug() { for (int i = 0; i < L; i++) { printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], end[i]); for (int j = 0; j < 26; j++) printf("%2d", next[i][j]); printf("]\n"); } }};char str[maxn];Trie ac;string pat;int main() { int T; scanf("%d", &T); while (T--) { int n; ac.init(); scanf("%d", &n); pat.clear(); for (int i = 0; i < n; i++) { scanf("%s", str); ac.insert(str); if (strlen(str) > pat.size()) { pat = str; } } cin >> pat; ac.build(); int ans = ac.query(pat); printf("%d\n", ans); } return 0;}
转载地址:https://blog.csdn.net/weixin_43820352/article/details/108523156 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月25日 12时19分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
深入探讨Varnish缓存命中率
2019-04-27
Linux下文件如果没有权限不能被Apache访问
2019-04-27
Linux内核学习四库全书
2019-04-27
Linux内核模块编程入门
2019-04-27
使用Cacti监控你的网络Cacti的安装
2019-04-27
2011年6月编程语言关注度排行
2019-04-27
Varnish使用小结
2019-04-27
千万级并发HAproxy均衡负载系统介绍
2019-04-27
什么是A记录、MX记录、CNAME记录
2019-04-27
MongoDB简介
2019-04-27
Varnish purges 缓存清除
2019-04-27
Linux下redis安装部署
2019-04-27
水平切分与垂直切分
2019-04-27
MySQL引擎
2019-04-27
MySQL下的NoSQL解决方案HandlerSocket
2019-04-27
Apache服务器下使用 ab 命令进行压力测试
2019-04-27
查看Firefox中的缓存
2019-04-27
http header头设置反向代理不缓存
2019-04-27
配置MySQL主从复制
2019-04-27