單模式串匹配
BF 算法和 RK 算法
BM 算法和 KMP 算法

多模式串匹配算法
Trie 樹和 AC 自動機

一、單模式串匹配：

BF： 簡單場景，主串和模式串都不太長, O(m*n)

KP：字符集范圍不要太大且模式串不要太長， 否則hash值可能沖突，O(n)

naive-BM：模式串最好不要太長（因為預處理較重），比如IDE編輯器里的查找場景，命令grep； 預處理O(m*m), 匹配O(n)， 實現較復雜，需要較多額外空間.

KMP：適合所有場景，整體實現起來也比BM簡單，O(n+m)，僅需一個next數組的O(n)額外空間；但統計意義下似乎BM更快，原因不明.

二、多模式串匹配：

naive-Trie: 適合多模式串公共前綴較多的匹配(O(n*k)) 或者 根據公共前綴進行查找(O(k))的場景，比如搜索框的自動補全提示.

AC自動機: 敏感詞匹配 適合大量文本中多模式串的精確匹配查找, 可以到O(n).

總結

以上是生活随笔為你收集整理的【数据结构与算法】【应用】字符串匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

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