UVA11019 Martix Matcher

題目描述：

給定一個\(n*m\)的文本串

問一個\(x*y\)的模式串出現的次數

?

AC自動機的奇妙使用

將\(x*y\)的模式串拆分成x個串，當x個串在同時被匹配時，認為原串被匹配

但是要區分匹配的行的差別，因此額外的附加一個二維數組\(cnt\)來表示匹配情況

記\(cnt(i,j)\)表示以\((i,j)\)為左上角的大小為\(x*y\)矩陣匹配了多少行。

將模式串拆成x個串，建成AC自動機

把文本串的n行放進去分別匹配，當枚舉到文本串中的第i行第j個字符時，

如果匹配上了模式串中第k行，那么\(cnt(i - k, j - y + 1) +1\)

最后的答案即為\(\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} [cnt(i,j)==x]\)

?

復雜度O(\(T(n*m+x*y)\))

?

但是，本題很坑

1.模式串可能有相同的兩行，盡管模式串行結尾的fail指針不會互指，但是這種情況下要用鏈表儲存

2.每次清AC自動機不要整個全部清，會帶來極大的復雜度

3.盡量不要以1作為下標，討論將變得很復雜

4.哈希的常數更優

5.本題卡常，如果過不去，考慮哈希

?

代碼在此

轉載于:https://www.cnblogs.com/reverymoon/p/8882299.html

總結

以上是生活随笔為你收集整理的UVA11019 Martix Matcher --- AC自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。