当前位置: 首页 > news >正文

temp

3.\(AC\)自动机

前言

兴许是字典树上的树上的 \(kmp\) ? \(O(n \times |C|)\) \(C\) 是字符集的大小,跑起来回比 \(O(n)\) 慢, 但是 \(|C|\) 的部分常熟小就是了.

介绍

\(kmp\) 与字典树结合产物.\(kmp\) 只能处理单个模式串或者文本串, 而 \(AC\) 自动机可以处理多个模式串, \(AC\) 自动机的 \(fail\) 指针(失配指针)可以理解成在字典树上找一个前缀使得其能与当前状态匹配最长的后缀.如果我们只插入一条模式串,不难发现这就是 \(kmp\)\(border\) 的过程.

图片来自 \(oi\) \(wiki\)

实现

\(fail\) 指针构建

约定

  • 首先考虑只有一个模式串的情况,这个 \(fail\) 指针不能指向自己.
  • 对于一个没有被修改过的用于指向子节点的指针可以看做指向 \(Null\) 节点, 根节点是 \(1\) 号节点.
  • \(Null\) 节点约定为 \(0\) 号节点

构建

  • 考虑广搜构建
  • 当前节点编号为 \(i\) 的子节点的 \(fail\) 指针应该指向当前节点的 \(fail\) 指针指向的节点的编号为 \(i\) 的子节点的 \(fail\) 指针,有几种情况,为了方便我们将当前节点编号为 \(i\) 的子节点的叫做 \(to\), 当前节点的 \(fail\) 指针指向的节点的编号为 \(i\) 的子节点的 \(fail\) 指针叫做 \(nxtfail\)
    • 两个子节点都存在,只要 \(to\)\(fail\) 赋值为 \(nxtfail\) 就可以了

    • \(nxtfail\) 不存在, 此时 \(nxtfail\) 指向 \(Null\) 节点,而 \(Null\) 的子节点的指针又指向 \(Null\),我们只需让 \(Null\) 的子节点的指向 \(root\) 节点就可以, 正确性显然,相当于失配后又从根节点开始

    • \(to\) 不存在直接将 \(to\) 赋值为 \(nxtfail\) 就可以了相当于跳 \(fail\)

    • 对于 \(1,2\) 情况的 \(to\) 应该入队, \(3\) 情况由于节点不存在不应当入队

    • (推荐左值引用的写法)

  • 不难发现 \(fail\) 指针会构成一棵树,因为 \(fail\) 指针指向的节点的深度一定更低.

【模板】AC 自动机

一个多模式串匹配单个文本串,考虑一个朴素的方法, 我们在字典树上"插入"文本串, 如果下一个节点空了就跳 \(fail\) , 由于我们已经处理了使得所有空的子节点都指向了 \(fail\), 插入时按照正常的方法插入就好了.对于 \(s\) 经过得每个节点 \(cnt++\), 代表一个方案数.考虑只有一个模式串时,不难发现上面的过程相当于 \(kmp\) ,最后的节点的方案数就是我们所要的方案数.多个模式串时由于某个的模式串可能包含其他模式串, 这时我们将 \(fail\) 的入度为零的节点的方案数向上加, 然后更新 \(fail\) 的入度.不难发现上述方法就是个拓扑.询问某个模式串的出现的个数,访问其在字典树上最后一个节点的 \(cnt\) 即可.

#include<bits/stdc++.h>
#define rep(i, l, r) for(ll i=(l);i<=(r);i++)
using namespace std;
typedef long long ll;const ll N = 2e5 + 10, M = 2e6 + 10;
ll n, m;
namespace AC {ll root, node_cnt;struct node {ll son[26], fail, ru, ans, bl;inline ll& operator[](ll x) { return son[x]; }}tr[N];ll Map[N], bl_cnt;inline ll newnode(){return ++node_cnt;}inline ll newbl(){return ++bl_cnt;}inline void init(){node_cnt = 0, root = newnode();}inline void ins(const char *s, const ll id) {ll len = strlen(s + 1);ll x = root;for (ll i = 1; i <= len; i++) {ll son = s[i] - 'a';if (tr[x][son] == 0)tr[x][son] = newnode();x = tr[x][son];}if (tr[x].bl == 0) tr[x].bl = newbl();Map[id] = tr[x].bl;}inline void build_Fail() {queue<ll> q;for (ll i = 0; i < 26; i++) tr[0][i] = root;q.emplace(root);while (!q.empty()) {ll x = q.front();q.pop();for (ll i = 0 ; i < 26; i++) {ll &to = tr[x][i];ll nxtfail = tr[tr[x].fail][i];if (to) {tr[to].fail = nxtfail;tr[nxtfail].ru++;q.emplace(to);}else to = nxtfail;}}}inline void query(const char *s) {ll len = strlen(s + 1);ll x = root;for (ll i = 1; i <= len; i++) {x = tr[x][s[i] - 'a'];tr[x].ans++;}}ll ans[N];inline void topu() {queue<ll> q;for (ll i = 1; i <= node_cnt; i++) if (tr[i].ru == 0) q.emplace(i);while (!q.empty()) {ll x = q.front(), fail = tr[x].fail;q.pop();ans[tr[x].bl] = tr[x].ans;tr[fail].ans += tr[x].ans;if (--tr[fail].ru == 0) q.emplace(fail);}}inline void Answer() {for (ll i = 1; i <= n ; i++) {cout << ans[Map[i]] << endl;}}
}
char s[M];
bool Memory_end;int main() {AC::init();scanf("%lld", &n);rep(i, 1, n) {scanf("%s", s + 1);AC::ins(s, i);}AC::build_Fail();scanf("%s", s + 1);AC::query(s);AC::topu();AC::Answer();return 0;
}
http://www.hskmm.com/?act=detail&tid=21088

相关文章:

  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单
  • 详细介绍:视频融合平台EasyCVR构筑智慧交通可视化管理与智能决策中枢
  • docker 在x86上build arm 镜像
  • 9.29软工
  • 不一样的.NET烟火,基于Roslyn的开源代码生成器
  • 复刻江协旋钮控制模块
  • 告别硬编码!5个让Web自动化脚本更稳定的定位策略
  • 从零开始,使用Idea工具搭建一个springboot项目
  • 最优/极值问题的算法选择
  • 第三方控件库的添加和使用
  • C4NR PVP服务器1.2 天穹炮塔更新
  • 树形dp [JOI Open 2020] 发电站 / Power Plant
  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题