专题·AC自动机
创始人
2024-03-07 07:54:57
0次

初见安——！！这里是咕咕咕好久好久的樱狸QvQ

考完初赛了 有一点点的空闲时间 来整理一下博客【因为发现忘性很大……超过一个月没用的东西就记不住了QAQ

前置知识：KMP，tire树。

一、AC自动机

其实AC自动机就是在tire树上KMP。

举个例子：给你一个串S，一个串T，求T在S中出现的次数。显然KMP线性匹配。

那么如果给你一个串S，很多串T，问你每个串在S中的出现次数呢？复杂度就不保了。这时就要用到AC自动机。

比如给的是abc，aab，abcba，acb，S串是abccbacbabcba。

我们对给的串建tire树：【图丑求放过

然后在这颗树上跟着走串S。

比如我们给这个图的点编号后，

s串abccbacbabcba会依次走过：1，4，5，然后发现下一个没有c了跳不动。

根据KMP的思想，我们在trie树上令fail指针表示与KMP类似的含义，也就是失配指针。fail[i]表示trie树上从根到当前点形成的字符串的后缀匹配前缀的最长串的结尾位置。那么上图的树中我们就可以建立fail指针：

没有连边的都是指向根节点】

这样一来，当S失配后，就会沿着fail往回跳，缩小匹配的字符串。而S走的全过程中的子串都不重复，因为每走一步必然会相较于前一步多了第i个字符。所以每次形成的字符串的后缀都是答案之一。

接着上文的例子，S失配没法跳c后回到根节点0，然后继续跳b，失配；跳a，跳到1,8,9；然后回到0……

我们在trie树上记录每个点为末尾代表了哪些字符串，然后就可以统计答案了。

看一个例题吧：洛谷 【模板】AC自动机（简单版）

看看代码吧——

#include
#include
#include
#include
#include
#include
#include
#define maxn 1000006
using namespace std;
typedef long long ll;
int read() {int x = 0, f = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();return x * f;
}int n, t[maxn][26], fail[maxn], num[maxn], tot = 0;
char s[maxn];
void add() {//建立trie树register int len = strlen(s), p = 0;for(int i = 0; i < len; i++) {int u = s[i] - 'a';if(!t[p][u]) t[p][u] = ++tot; p = t[p][u];}num[p]++;//表示以p结尾的字符串数
}queue q;
void build() {for(int i = 0; i < 26; i++) if(t[0][i]) q.push(t[0][i]);//bfs建立fail指针while(q.size()) {register int u = q.front(); q.pop();for(int i = 0, v; i < 26; i++) {v = t[u][i];if(v) fail[v] = t[fail[u]][i], q.push(v);//如果有儿子，就匹配过去else t[u][i] = t[fail[u]][i];//没有的话相当于路径压缩，直接连过去}}
}int ans = 0;
void AC() {register int len = strlen(s), p = 0;for(int i = 0, u, v; i < len; i++) {u = s[i] - 'a';  p = t[p][u], v = p;while(v && num[v] != -1) {//暴力跳fail查询ans += num[v], num[v] = -1;v = fail[v];}}
}signed main() {n = read();for(int i = 1; i <= n; i++) scanf("%s", s), add();build(); scanf("%s", s); AC();printf("%d\n" , ans);return 0;
}

（未完待续 咕太久了我也忘了后续要写啥QAQ

上一篇：傻白入门芯片设计，三大基本定律（十）

下一篇：Espresso Sequencer：去中心化Rollups

相关内容

热门资讯

宗亲联谊大会主持词 宗亲联谊大会主持词　　主持词要注意活动对象，针对活动对象写相应的主持词。在人们越来越多的参与各种活动...
和谐之声新春联欢会主持台词稿 和谐之声新春联欢会主持台词稿　　(联欢会开场前60分钟内，所有接待、服务、道具、灯光、音响、服装、化...
遗体告别主持词 2021遗体告别主持词范文（通用5篇）　　主持词是各种演出活动和集会中主持人串联节目的串联词。在当下...
颁奖典礼主持词 关于颁奖典礼主持词（通用5篇）　　主持词是各种演出活动和集会中主持人串联节目的串联词。在各种集会、活...
高中学生家长会主持词 高中学生家长会主持词汇编　　许多家长把注意力集中在孩子的学习上，其实，作为家长更应该从侧面关心孩子的...
公司元旦晚会活动主持词 公司元旦晚会活动主持词　　主持词分为会议主持词、晚会主持词、活动主持词、婚庆主持词等。现今社会在不断...
开业主持词 开业主持词龙腾四海,凤舞九天;光辉酒店,鸿业竣开！香飘万家,技艺精湛;四面得利,八方进财!尊敬的各位...
师德师风演讲比赛主持稿 师德师风演讲比赛主持稿范文（通用7篇）　　在快速变化和不断变革的今天，很多地方都会使用到主持稿，主持...
结婚仪式主持词 结婚仪式主持词10篇　　主持词是各种演出活动和集会中主持人串联节目的串联词。我们眼下的社会，主持人参...
企业年会主持词开场白精选 　　新年拉近了我们成长的距离，新年染红了我们快乐的生活。下面是CN人才网小编为大家整理的年会主持词开...
教师节座谈会校长致辞 教师节座谈会校长致辞（精选16篇）　　在日常学习、工作抑或是生活中，大家对致辞都再熟悉不过了吧，在各...
五一晚会开幕词与闭幕词 五一晚会开幕词与闭幕词　　在当今社会生活中，我们经常都会使用到开幕词，开幕词对引导会议或活动顺利进行...
含笑半步颠经典台词 含笑半步颠经典台词　　在社会发展不断提速的今天，我们使用上台词的情况与日俱增，台词是构成一个剧本的基...
中秋节主持词
联谊会主持词 有关联谊会主持词集合8篇　　主持词是各种演出活动和集会中主持人串联节目的串联词。在人们积极参与各种活...
晚会闭幕词 晚会闭幕词（通用37篇）　　在日新月异的现代社会中，很多情况下我们需要用到主持稿，主持稿起到承上启下...
婚礼主持词 婚礼主持词（精选20篇）　　主持词要注意活动对象，针对活动对象写相应的主持词。在人们越来越多的参与各...
半年总结会主持词 半年总结会主持词　　以下是由应届毕业生网PQ小编为大家整理出来的半年总结会主持词，仅供参考，半年总结...
最短的对口相声台词 最短的对口相声台词范文　　相声是一种中国曲艺表演艺术，源于华北，流行于京津冀，普及于全国及海内外，始...
司仪主持词 精选司仪主持词（精选14篇）　　主持词需要富有情感，充满热情，才能有效地吸引到观众。在各种集会、活动...