-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.go
150 lines (122 loc) · 2.19 KB
/
trie.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package util
import (
"strings"
)
type Node struct {
//rune表示一个utf8字符
char rune
Data interface{}
parent *Node
Depth int
//childs 用来当前节点的所有孩子节点
childs map[rune]*Node
term bool
}
type Trie struct {
root *Node
size int
}
func NewNode() *Node {
return &Node{
childs: make(map[rune]*Node, 32),
}
}
func NewTrie() *Trie {
return &Trie{
root: NewNode(),
}
}
//假如我要把 敏感词: “我操”
// Add("我操", nil)
// Add("色情片", nil)
func (p *Trie) Add(key string, data interface{}) (err error) {
key = strings.TrimSpace(key)
node := p.root
runes := []rune(key)
for _, r := range runes {
ret, ok := node.childs[r]
if !ok {
ret = NewNode()
ret.Depth = node.Depth + 1
ret.char = r
node.childs[r] = ret
}
node = ret
}
node.term = true
node.Data = data
return
}
// findNode("色情片")
func (p *Trie) findNode(key string) (result *Node) {
node := p.root
chars := []rune(key)
for _, v := range chars {
ret, ok := node.childs[v]
if !ok {
return
}
node = ret
}
result = node
return
}
func (p *Trie) collectNode(node *Node) (result []*Node) {
if node == nil {
return
}
if node.term {
result = append(result, node)
return
}
var queue []*Node
queue = append(queue, node)
for i := 0; i < len(queue); i++ {
if queue[i].term {
result = append(result, queue[i])
continue
}
for _, v1 := range queue[i].childs {
queue = append(queue, v1)
}
}
return
}
func (p *Trie) PrefixSearch(key string) (result []*Node) {
node := p.findNode(key)
if node == nil {
return
}
result = p.collectNode(node)
return
}
// text = "我们都喜欢王八蛋"
// replace = "***"
func (p *Trie) Check(text, replace string) (result string, hit bool) {
chars := []rune(text)
if p.root == nil {
return
}
var left []rune
node := p.root
start := 0
for index, v := range chars {
ret, ok := node.childs[v]
if !ok {
left = append(left, chars[start:index+1]...)
start = index + 1
node = p.root
continue
}
node = ret
if ret.term {
hit = true
node = p.root
left = append(left, ([]rune(replace))...)
start = index + 1
continue
}
}
result = string(left)
return
}