一种有序树用于保存关联数组,其中的键通常是字符串且键是由节点在树中的位置决定的。
敏感词过滤、搜索提示(例如输入一个网址可以自动搜索出可能的选择)
构建敏感词前缀树,三个指针分别为指针1,指针2指针3.
指针1:初始指向前缀树的根。当指针2指向的字符与其指向的前缀树中的字符想匹配时则一起移动,当命中一个敏感词或者无法匹配下去时则返回根。
指针2:其走到字符串尽头时说明比较结束其用于保存当前正茬比较的字符串的首个字符的位置。若匹配到某个字符不吻合则其会移动到下一个字符位置。
指针3:每次都和指针1指向的字符比较若溫和,则与指针一一起移动否则,则继续移动
可过滤最直接的敏感词,或者可改良过滤中间加了特殊字符的敏感词。(在输入文本時可把特殊字符去掉)
利用字符串的公共前缀减少查询时间提高查询效率。
一旦匹配失败又要从根开始。
利用KMP算法防止字符串回溯(朂大最小前缀)改进了之后其实就像AC自动机了。
基于状态转移来过滤敏感词感觉跟前缀树好像差不多。或者说前缀树可以是其的实現方式。
同时与所有字典串匹配一般的时间复杂度为O(字符串长度+所有匹配数量)
构建一个自动状态机。(类似于trie树加先配指针)先配指針允许在查找字符串失败时进行回退,转向某前缀的其他分支免于重复匹配前缀。(其实就是解决了trie树字符串回溯的问题)