标签为 [AC自动机] 的文章

BZOJ 2434 阿狸的打字机

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P,则求出y==当前P的次数的所在节点的子树大小。 如果为B,删去当前节点的影响,返回它的父亲 否则 加入,加上当前节点的影响 可以用树状数组维护 Code: #include<cstdio> #include<algorithm> #in ......

BZOJ 2746 旅行问题

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预处理)   Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MOD=1e9+7; int pos[2100000],dep[1100000],q[1100000], ......

BZOJ 1030 文本生成器

啦啦啦,我这种蒟蒻也只能写这些水题了。 话说czy的模板并不是特别好懂诶@RetardedZY。 这道题其实就是你先把这些合法字符串放进AC自动机。 由于要求的是长度为m的包涵其中一个合法字符串的方案数, 则你可以用AC自动机求出不合法的方案数, 然后用总方案数减去它就可以了。 代码也很短。 Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; using namespace std; const int MOD=10007; int ans,n,m,num; int trans[6100][27],pre[6100],f ......

HihoCoder1036 AC自动机模板

这只是一份模板 AC自动机 code #include&lt;stdio.h&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; using namespace std; int n,len,num,son[1000005][26],que[1000005],head,tail,hz[1000005],k1,k2; char st[1000005],st1[1000005]; bool flag[1000005],val[1000005]; int main(){ scanf("%d",&amp;n); num=1; for(int i=1;i&lt;=n;i++){ scanf("%s",st); ......