@xzyxzy
2018-07-02T18:15:00.000000Z
字数 3980
阅读 1731
字符串
，中文名自动机，是图的一种，实现高效多串匹配单串的一种字符串算法
跟踪dalao的blog
树上令一个点表示从根到它的串，那么一个点的fail指向和它拥有最长后缀的串（所以可以指向）
1
用来多串匹配单串或多串，效率高于（可以代替），但是字符集很大时候需要大空间或用时间换空间（开）
2
套路:表示到第号节点（长串匹配到），匹配长度为（短串匹配到）的方案数啥的
! 是一棵树，但是自动机是图，可以存在环（病毒）
! 构造数据的时候，可以检查自己写的自动机是否可以从第一位开始匹配
洛谷3808模板1
首先建出树（），然后通过算出，再进行匹配
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<queue>#define end end1using namespace std;const int MAXN=1000100;int ch[MAXN][26],end[MAXN],fail[MAXN];char s[MAXN];int N,node;queue<int> Q;void Build(){int len=strlen(s),x=0;for(int i=0;i<len;i++){if(!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++node;x=ch[x][s[i]-'a'];}end[x]++;}void Get_Fail(){for(int i=0;i<26;i++) if(ch[0][i]) Q.push(ch[0][i]);while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;i<26;i++)if(ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],Q.push(ch[x][i]);else ch[x][i]=ch[fail[x]][i];}}int AC(){int len=strlen(s),x=0,ans=0;for(int i=0;i<len;i++){x=ch[x][s[i]-'a'];for(int p=x;p&&~end[p];p=fail[p])ans+=end[p],end[p]=-1;}return ans;}int main(){cin>>N;while(N--){scanf("%s",s);Build();}Get_Fail();scanf("%s",s);printf("%d\n",AC());return 0;}
[luogu3808]【模板】AC自动机（简单版）
把模式串的AC自动机建好后用文本串匹配，匹配完成就删去此串及其后缀
[luogu3796]【模板】AC自动机（加强版）
[CJOJ1435] 【模板题 USACO】AC自动机
[BZOJ3172][TJOI2013]单词
统计每个模式串出现次数，匹配时打个标记，然后用树DFS完成统计数量
[HDU2296]Ring
表示母串匹配到第位，匹配到AC自动机上第个节点的最大权值，同时记录表示选择的方案
[BZOJ1030][JSOI2007]文本生成器
表示生成文本长度为，匹配到AC自动机上第个节点的没有出现认识的单词的方案数，最后用总方案减去所有不合法方案即为答案
[Luogu2444][POI2000]病毒Hard
如果AC自动机上出现了没有标记的环那么就存在无限长的串使得不存在任何模式串
[BZOJ1009][HNOI2008]GT考试Hard
表示长串枚举到短串匹配到的方案数，由于短串很短，所以另表示短串从上次匹配的下一位将要匹配从而匹配/失配到了的方案数，使用矩阵乘法，表示枚举下一位数字是几来更新方案数
[BZOJ3530][SDOI2014]数数Hard
数位DP，表示数字有位，AC自动机上匹配到第个节点，比小/等/大的方案数，最后统计位数比小的所有答案以及位数等于的
[Luogu3121][USACO15FEB]审查CensoringHard
建好AC自动机后跑匹配，记录匹配母串中每个字符出现的位置，如果遇到节点那么回到该词前一个字符的位置，继续向下匹配
[BZOJ1212][HNOI2004]L语言Hard
AC自动机：可以识别的是若干个区间，从起点起，能够被搜到的最右端节点即为答案
Trie树DP：字符串反转后建，表示能否被识别，当是树上的一个单词的时候
[Luogu3041][USACO12JAN]视频游戏的连击Video Game Combos
表示母串长度为，匹配到AC自动机上第个节点的最大分数