AC自動機

思想:

相當于在trie樹上的KMP。

流程:

1.建構trie樹

注意0為根會友善很多。

2.get_fail()

雖然和KMP很相似，我舉一反三的能力有限，是以還是要重新講qwq

fail[i]：表示滿足i為結尾的字尾與rt開始的字首比對的最大長度。

求法為了無後效性，用BFS（按層周遊），每次枚舉相鄰的trie樹繼續比對下去，比對不明顯，但是很短，巧妙地運用了fail和trie的性質。

3.文本串在trie樹上浪

從跟開始，記錄u指針，逐漸往下，每跳一步，不能局限于目前的格局，還要一直疊代到fail=0為止，當然原指針為止不變。

你會發現如果u走不下去了，就會自動為0，到根節點【1明白了吧】，重新比對。

當然不用想這麼多，AC制動機是個DFN，隻要暴力往下走就行了。

代碼：

題意：給了您很多串，您要構造一個K位的文本串，求包含串數的最大值。

思路:fail+dp（trie樹上的）

首先我們fail利用它“字尾=字首”的性質，預處理出cnt​​i​​\(cnt[i]=\)(本身trie預處理時有無串)

\(cnt[i]+=cnt[fail[i]]\)(顯然）

狀态：dp[i][j]是：按i下第i下為trie樹上的j的得分

\(dp[i+1][trie[j][i]]=dp[i][j]+cnt[j]\)

代碼: