AC自動機習題。

A

C

AC

AC自動機習題。

前話：

AC自動機常用于解決多模式字元串比對問題，主要運用到了

T

r

i

e

+

k

m

p

Trie+kmp

Trie+kmp的思想，而

kmp

kmp是單模式字元串比對，求

f

a

l

fail

fail與

kmp的

n

x

t

[

]

next[]

next[]數組類似的思想，隻不過

fail是記錄最大字尾，

next[]最大前字尾。

都能在

O

(

)

O(n)

O(n)複雜度内解決問題。但是暴力的跳

fail會浪費很多時間，導緻一個結點被多次通路，是以考慮樹上跑拓撲優化。

思路：闆子題，不多說，具體看代碼。

思路：求出現次數最多的字元串，我們隻需用一個

c

cnt[]

cnt[]數組改為維護最後一次出現的模式串的編号，然後用

v

s

vis[]

vis[]數組記錄答案。

題意：求每個模式串在文本串中出現的次數，可能含重複串。

因為可能含重複串，是以我們需要用一個數組

b

j

bj[]

bj[]來标記第一次在字典樹的出現的模式串對應的編号。因為之前的跳

fail都是暴力跳的，一個結點可能會被重複通路多次，很浪費時間，是以我們考慮在字典樹上跑拓撲，以

fail為一條出邊，進行拓撲狀态轉移，從入度為0的開始跑，這樣每個結點就不會重複通路了。

4.P3966 [TJOI2013]單詞

思路：把單詞用

#

\#

#連接配接起來成為文本串，然後跑

AC自動機即可。

注意打

ans[]

ans[]标記的時候，特判一下

#，遇到

#，目前結點

u

u歸0.

坑點：字元串大小應該開大點，之前開得太小，調了好半天。