dfa 算法

1. 创建字典树
2. 对输入的词典进行匹配

创建节点 这里的结点就是上面那幅图

package DFAtype Node struct {//结束End bool//节点Next map[rune]*Node
}// AddChild  add char
func (n *Node) AddChild(c rune) *Node {if n.Next == nil {n.Next = make(map[rune]*Node)}// 这个字符存在 直接返回if node, ok := n.Next[c]; ok {return node} else {n.Next[c] = &Node{End:  false,Next: nil,}}return n.Next[c]
}// FindChild find char
func (n *Node) FindChild(c rune) *Node {if n.Next == nil {return nil}if node, ok := n.Next[c]; ok {return node}return nil
}// AddWords add words
func (n *Node) AddWords(w string) {node := nr := []rune(w)for i, _ := range r {node = node.AddChild(r[i])}node.End = true
}

AddChild 字典树中添加字符
FindChild 查询字符
AddWords 添加单词

package DFAtype DFAMatcher struct {Root *Node
}func NewDFAMatcher() *DFAMatcher {return &DFAMatcher{Root: &Node{End: false,},}
}
func (D *DFAMatcher) Build(strings []string) {for i := range strings {D.Root.AddWords(strings[i])}
}//  Match 匹配
func (D *DFAMatcher) Match(text string) bool {runes := []rune(text)child := D.Rootfor i := 0; i < len(runes); i++ {//如果没有 ，就往下面找findChild := child.FindChild(runes[i])if findChild == nil {//如果没有匹配 在差从根节点查询node := D.Root.FindChild(runes[i])if node == nil {continue}//把当前节点给查询节点child = nodecontinue}if findChild.End == true {return true}//把根节点换成当前节点child = findChild}return false
}

Build 构建字典树
Match 匹配铭感词 // true 存在 false 不存在
这里的Match（）方法可以抽一个接口出来，这样可以自定义我们别的过滤算法