下面是數組模拟：
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那麼就會出錯，是以我們用狀态壓縮來表示必須包含的串有多好個，還有這裡會存在串包含串的情況，是以要在構造時處理，否則會出錯的。