1#include<stdio.h>2#include<stdlib.h>3#include<time.h>4#include<conio.h>567//行宽度8#defineROW_LEN3891011//比特位域结构12typedefstructbitsbits;13...

托米的咒语（序列自动机）  AC_Code1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=3e3+10;5constintinf=0x3f3f3f3f;6#definerep(i,fi...

月月查华华的手机（序列自动机）    AC_Code1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=1e6+10;5constintinf=0x3f3f3f3f;6...

序列：不要求连续子串：要求连续AC自动机，kmp都是匹配子串的；序列自动机是匹配序列的参考博客：https://www.cnblogs.com/31415926535x/p/10504504.html序列自动机实质还是用空间换时间，它有一个数组 nxt[i][j](nxt[maxn][26]），表示原串s的第...

指针方式：1/*KeywordsSearch*/2#include<iostream>3#include<stdio.h>4#include<string.h>5#include<string>6#include<cstdlib>7#include<ct...

原文：https://blog.csdn.net/u013421629/article/details/83178970一道bat面试题：快速替换10亿条标题中的5万个敏感词，有哪些解决思路？有十亿个标题，存在一个文件中，一行一个标题。有5万个敏感词，存在另一个文件。写一个程序过滤掉所有标题中的所有敏感词，保存到另一个...

题意：给出n个模式串和一个文本串，问在文本串中出现了几个模式串。思路：AC自动机裸题；看过n个版本的AC自动机后终于理解了代码是如何实现的。再一次体会到光懂得原理和能利用原理解决问题之间的巨大的鸿沟。代码：#include<iostream>#include<cstdio>#include<...

　　 先给出一些模式串，然后给出一个母串，统计先前给出的模式串中，有多少个在母串中出现。多组数据。　　AC自动机模板题。　　首先根据输入数据构建AC自动机。　　然后对于每一位，沿着fail指针走，全部统计并累加。　　有一个小小的优化，就是走过的都标记为-1，下次碰到-1就不走了。因为如果这个节点的标记为-1，...

　　给出一堆串，然后求一个包含这些串的所有串的最短的中的字典序最小的。 　　先造一个AC自动机，多模匹配嘛。　　然后bfs在AC自动机上面走，两维状态，dis[i][j]表示已经走到过的串状态为i，在AC自动机上面的位置为j的最短距离。　　然后这题居然要卡空间！　　坑死了。　　然后用了short　　wa掉了。...

 　　给出n个模式串，问长度为m的串中有多少个至少含有这n个模式串中的任意一个。　　注意，所有的串仅由A~Z26个大写字母构成。 　　AC自动机好题。　　先构建一个AC自动机。　　然后在AC自动机上面跑dp。　　建议开滚动数组。　　dp[i][j]表示长度为i，在AC自动机上面走到了j的方案数。　　...

原文链接www.cnblogs.com/zhouzhendong/p/PAM.html无。（强行说和KMP有关也是可以的……）1.一个长度为n的字符串最多有n个本质不同的回文子串。2.对于一个字符串S，如果在其之后新插入一个字符，那么最多产生一种新的回文子串。　证明：　　假设加入这个字符之后...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF-100543G.html　　你可以对一个字符串进行以下两种操作：　　1. 在其头或者尾部加入一个新字符　　2. 翻转当前字符串，并把他拼接在当前字符串的前面或者后面　　给你T组询问，每组询问一个字符串，问你至...

原文链接http://www.cnblogs.com/zhouzhendong/p/8196279.html　　引用一下lych大佬的：　　在字母只有前alphabet时，给定N个串，求长度为len的串包含这些N个串的个数最大值的期望值。　　我们首先发现总共的字符个数才就75个，那么闭着眼睛先建一个AC自动机，Trie...

　　现在有一个长度为n(n<=2000000000)的DNA串，其中只可能有A、C、G、T四种字母。现在给出m(m<=10)个危险串(len<=10)，求有几种可行的安全串。最终的答案mod100000。　　我们先按照输入的危险串构建AC自动机。　　对于当前串在AC自动机上的某一个状态k，我们接下来填...

 参考：陈立杰的课件参考1...