每日總結-05-14

為了準備區域賽，決定每天都寫一個總結，記錄一下今天做了什麼事情，如果沒做啥有意義的事情，就不總結了。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

今天學習了AC自動機的算法，感覺AC自動機好神奇。又會做了好多題，好高興啊！

AC自動機本身是一個模版。

AC自動機建的一棵樹中，每一個節點都有一個fail指針。每個節點的fail指針指向的是目前比對串的字尾。

即：she可以指向he，he可以指向e。

建完了AC自動機的樹之後，就可以根據自己的需求，開始在AC自動機的樹上跑資料了。

1，hdu-2222-Keywords Search

基礎的AC自動機模闆題，就是建立一顆AC自動機的樹，然後進行比對。

代碼連結：

2，hdu-2896-病毒侵襲

同上題。

3,hdu-3065-病毒侵襲持續中

同上題，無非是加了一個統記單詞出現的次數。

4，zoj-3430-Detect the Virus

很惡心人的題目。錯了N遍，注意标記。

注意翻譯過來的字元串可能是0~255之間的。

5，poj-2778-DNA Sequence

算是AC自動機的進階題。

AC自動機+DP+矩陣優化

明白轉移的過程，每次轉移，就相當于把乘一次。

矩陣學的好了，這個過程了解起來很簡單。

最後的結果就是矩陣的n次方。

6，hdu-2243-考研路茫茫――單詞情結

這一道題目算是上一道題目的進階版。

假如最後建構的矩陣是A。

那麼這道題目就是求：26^1+26^2+..+26^l-(A^1+A^2+...+A^l)

這裡面就用到了等比矩陣求前n項和。說起來就是兩次二分。之前刷矩陣專題的時候有刷到過。

代碼連結: