AC自動機總結

1.N個字元串作為字典，和一個長字元串，詢問長字元串中出現了多少字典中的串

AC自動機，把待比對的字元串放在自動機上奔跑，每到達一個ed節點都打上一個已到辨別，

然後向ta的fail奔跑

因為隻用計算出現了多少個字典串，不要求統計具體個數，

是以每次遇上一個打過标記的節點就不用再沿fail跑了

2.N個字元串作為字典，和一個長字元串，詢問長字元串中出現了多少字典中的串并統計個數

字典建立AC自動機，建立fail樹，在AC自動機上奔跑，經過的節點cnt++，

統計每個單詞出現個數即統計fail樹上該節點所在子樹中的cnt

（這就是fail樹的性質，把所有fail指針反向後，包含該串的所有長串的ed就都到了該串ed所在的子樹中）

3.給出一個短串和N個長串，求多少個長串包含短串

把所有串建立AC自動機，建立fail樹，看一下每一個長串的每一個點是否出現在短串ed的子樹中

4.給出多個短串和多個長串，求每個短串出現在了幾個長串中

短串建立AC自動機，把長串放到自動機上比對，在比對過程中把經過的短串ed的cnt++

統計短串ed的權值即可

優化：單點打辨別，查詢子樹和，需要注意的是求短串的ed是取并集，

需要按照dfs序排序然後将相鄰的兩個點的lca-1，進行一個容斥

5.給出多個短串和多個長串，求每個長串中出現了幾個短串

把所有串建立一個AC自動機，在短串ed打标記，對于每一個長串，

統計ed到根的路徑上有多少标記，由于可能重複計算，我們就要應用容斥原理，

即按dfs序排序，在每一次統計時減去ta前一個節點和目前節點的lca的答案