树3:字典树(Trie树)
Trie 树,也叫“字典树”,它是一个树形结构,是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。是属于多模式匹配的一种解法。
Trie 树,也叫“字典树”,它是一个树形结构,是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。是属于多模式匹配的一种解法。
BF、RK、BM和KMP都是单模式匹配算法,也就是一个主串只能匹配一个模式串。在很多时候我们还需要多模式匹配,也就是一个主串匹配多个模式串,比如聊天敏感词。敏感词是一个列表,一个主串可能包含了多个敏感词。
KMP 算法是根据三位作者(D.E.Knuth,J.H.Morris 和 V.R.Pratt)的名字来命名的,算法的全称是 Knuth Morris Pratt 算法,简称为 KMP 算法。
BM(Boyer-Moore)算法,是一种高效的单模式串匹配算法。高效的字符串匹配算法在文本编辑器这样的软件上应用是否广泛。BM算法比著名的KMP算法更加高效。
字符串匹配可分为单模式串匹配和多模式串匹配,单模式串匹配就是一个串和一个子串匹配,多模式串匹配可以一个串同时查找多个字串。