专题·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

相关内容

热门资讯

远山者，宅之东，落凤山是也（... 远山者，宅之东，落凤山是也 篇一远山者，宅之东，落凤山是也落日余晖洒在窗前，映照着远山的轮廓，宛如一...
小学作文极速风车【优质3篇】 小学作文极速风车 篇一极速风车是一款非常受小学生欢迎的游乐设备。它由一个巨大的圆盘和一根中央轴组成，...
看图写话铲雪作文（推荐6篇） 看图写话铲雪作文 篇一冬天的早晨，大雪纷飞，整个小区都被染上了一片银白色的颜色。小明推开窗户，看着窗...
小松树小学作文（优秀6篇） 小松树小学作文 篇一：我的暑假生活暑假终于来了，我迫不及待地计划着如何度过这个美好的假期。首先，我决...
走进新时代小学作文【优选4篇... 走进新时代小学作文 篇一随着时代的发展，我们迎来了新时代小学。新时代小学是一座现代化的学校，拥有先进...
我的心儿怦怦跳小学生作文【优... 我的心儿怦怦跳小学生作文 篇一我的心儿怦怦跳今天，我要给大家讲一个有关我的心情的故事。故事的主人公是...
走进医院小学作文【优秀3篇】 走进医院小学作文 篇一医院小学是一所特殊的学校，它位于医院内，为住院的患儿提供教育服务。我有幸参观了...
父母的爱小学作文700字【实... 父母的爱小学作文700字 篇一父母的爱父母是孩子一生中最重要的人，他们的爱无处不在。我有一个特别疼爱...
美丽的秋天树叶小学作文【精彩... 美丽的秋天树叶小学作文 篇一秋天来了，大地变得金黄了起来。走在树林里，你会看到树叶一个个像小精灵一样...
买菜小学作文【优质6篇】 买菜小学作文 篇一我喜欢去菜市场买菜我家离菜市场很近，所以每次我都会去买菜。我喜欢去菜市场买菜的原因...
逛书店的作文（最新3篇） 逛书店的作文 篇一逛书店的作文近年来，随着电子书的兴起，逛书店的人似乎越来越少了。然而，对我来说，逛...
心儿怦怦跳小学作文（最新6篇... 心儿怦怦跳小学作文 篇一心儿怦怦跳我是一颗小小的心儿，每天都在孩子们的胸腔中怦怦跳动。当孩子们快乐时...
大力士小学作文（优选6篇） 大力士小学作文 篇一我的偶像我有一个偶像，他就是大力士先生。大力士先生是我们学校的保安，他不仅身手敏...
我的伙伴小学作文【精彩6篇】 我的伙伴小学作文 篇一 我的伙伴小学作文 篇二我的伙伴小学作文 篇三 　　一天，我在院子里玩耍，无意...
春节联欢晚会小学作文（通用6... 春节联欢晚会小学作文 篇一喜迎新春，迎接春节联欢晚会今年的春节联欢晚会真是精彩纷呈！我和家人一起坐在...
同一个屋檐下作文600字【精... 同一个屋檐下作文600字 篇一家是一个温暖的港湾，是每个人一生中最重要的地方。在同一个屋檐下生活，意...
养兔真让我着迷小学作文（实用... 养兔真让我着迷小学作文 篇一 我家养了一只可爱的小兔子，从那时起，我就对养兔子产生了浓厚的兴趣...
春天作文【通用6篇】 春天作文 篇一春天的美丽春天是四季中最美丽的季节之一。当冬天的寒冷逐渐消退，春天的阳光温暖地洒在大地...
牛奶的自述小学作文（精彩3篇... 牛奶的自述小学作文 篇一我是一杯牛奶，来自一头温柔的奶牛妈妈。在牧场上，我见证了奶牛妈妈们辛勤的劳动...
言而有信小学作文（推荐5篇） 言而有信小学作文 篇一：诚信的重要性诚信是一种美德，是一个人最基本的道德品质之一。作为小学生，我们更...