下面是数组模拟：
View Code
HDU 2896 病毒侵袭
题意：
之前指针做的链接：javascript:void(0)
现在数组模拟的代码：
HDU 3065 病毒侵袭持续中
题意：中文......
思路：
模板题的多模式串匹配，
ZOJ 3430 Detect the Virus
只要翻译之后就是很裸AC自动机匹配了，悲剧的，跳了n就不知道为什么老是sf
无语：
ps:后来改了老长时间还是不对，最后看了一下结题报告，这里最坑爹了。这里翻译后的字母在0-255之间 包括了’\0‘表示字符串的结束，如果我们中间翻译出了'\0'那么后边的字符就没有了，翻译后得到的字符也就不对了，MD查了n久，重写了n次。郁闷啊。。。
AC自动机+矩阵
pku 2778 DNA Sequence
给定n个病毒DNA串，求一个长度为m的DNA片段不包含任何一个病毒串的的可能数？
首先根据n个DNA串构造AC自动机，然后根据AC自动机构造矩阵，然后转化到Matrix大神的是个利用举证解决的问题的例八中去。
才开始我一直以为推出的举证和斐波那契数列的意思一样，转了个死弯，这里是把AC自动机这个图转化为邻接矩阵，然后求从一个状态到另一个状态经过m条边的的可能数。这个通过AC自动机得到的矩阵其实就是一个关系矩阵。
这里借鉴了一下胡浩大神的AC自动机模板：
HDU2243 考研路茫茫——单词情结
题意：中文..
首先看到的是至少包含一个词根，所以我们想到他的对立面，我们求出26^1 + 26^2 + ...... + 26^L 所有的可能的串，然后减去一个也不包含病毒串的数量，就求出了结果。
这里求要求模2^64 long long 是不能存下的怎么办？我们直接用unsigned long long 来表示他表示的最大值为2^64 - 1如果超过此值，他会直接回到0加起就相当于%2^64了。然后求和时有一个二分的方法求和a^1 + a^2 + ...... + a^k -》sum(a,k) 如果k是偶数： => sum(a,k/2) * (a^(k/2) + 1) 如果为奇数得：sum(a,k -1) + a^k 时间复杂度是log（L）然后利用AC自动机构造状态图，构造举证，转化为例8 求一个病毒串都不包含的情况，总数减去该数即可。
AC自动机+DP
pku 3691 DNA repair
or HDU 2457
指针解答：javascript:void(0)
数组模拟模板：
HDU 2825 Wireless Password
题意：
给定M个字符串，然后给出密码的长度为n ，字符串都是用小写字母组成的，求可能组成的密码，密码必须满足至少包含k个给出的字符串。
AC自动机那部分就不用说了，模板。关键是DP部分，dp[i +１][chd[j][l]][k|val[chd[j][l]]] += dp[i][j][k]; i 表示当前枚举的字符串的长度， j表示状态，k表示包含了几个给定串。这里的每个状态对应了2^10个可能。我们只要枚举经过i个字符串能够达到该状态的个数即可。
pku 1625 Censored!
给定n个可选字符，求组成长度为m的字符串不包含给定的p个病毒串的可能数。（出现的字符都是由n个给定字符组成）。
这在AC自动机DP里面算是简单的得了，不过这里涉及的大整数，所以显得有些复杂呢，这里直接用java的大整数写也就比较简单了。
dp[i][j] += dp[k][j -1] i表示状态j表示组成字符串的长度 k是i的父亲状态、
HDU 4534 郑厂长系列故事——新闻净化
一看就是AC自动机+D的题目，可是还是太弱看不出来。dp[i][j][k]表示但我们面临一个字符时的状态 i表示处理了i个字符，j表示树上的一个状态，k表示所必须包含的字符串包含了多好啊个。才开始我以为直接k表示包含了多少个不就行了吗，可是如果存在两个形同的串的值为999那么就会出错，所以我们用状态压缩来表示必须包含的串有多好个，还有这里会存在串包含串的情况，所以要在构造时处理，否则会出错的。