【資料結構與算法】【應用】字元串比對

1. 單模式串比對

   BF 算法和 RK 算法

   BM 算法和 KMP 算法

2. 多模式串比對算法

   Trie 樹和 AC 自動機

一、單模式串比對：

1. BF： 簡單場景，主串和模式串都不太長, O(m*n)
2. KP：字元集範圍不要太大且模式串不要太長， 否則hash值可能沖突，O(n)
3. naive-BM：模式串最好不要太長（因為預處理較重），比如IDE編輯器裡的查找場景，指令grep； 預處理O(m*m), 比對O(n)， 實作較複雜，需要較多額外空間.
4. KMP：适合所有場景，整體實作起來也比BM簡單，O(n+m)，僅需一個next數組的O(n)額外空間；但統計意義下似乎BM更快，原因不明.

二、多模式串比對：

1. naive-Trie: 适合多模式串公共字首較多的比對(O(n*k)) 或者 根據公共字首進行查找(O(k))的場景，比如搜尋框的自動補全提示.
2. AC自動機: 敏感詞比對 适合大量文本中多模式串的精确比對查找, 可以到O(n).