-
Notifications
You must be signed in to change notification settings - Fork 0
/
node.go
98 lines (88 loc) · 2.14 KB
/
node.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
package gstring
type node struct {
children map[rune]*node
fail *node
depth int
end bool
}
func (n *node) add(word string) {
chars := []rune(word)
if len(chars) == 0 {
return
}
nd := n
for i, char := range chars {
if nd.children == nil {
child := new(node)
child.depth = i + 1
nd.children = map[rune]*node{char: child}
nd = child
} else if child, ok := nd.children[char]; ok {
nd = child
} else {
child := new(node)
child.depth = i + 1
nd.children[char] = child
nd = child
}
}
nd.end = true
}
func (n *node) build() {
var nodes []*node
for _, child := range n.children {
child.fail = n
nodes = append(nodes, child)
}
for len(nodes) > 0 {
nd := nodes[0]
nodes = nodes[1:]
for key, child := range nd.children {
nodes = append(nodes, child)
cur := nd
for cur != nil {
if cur.fail == nil {
child.fail = n
break
}
if fail, ok := cur.fail.children[key]; ok {
child.fail = fail
break
}
cur = cur.fail
}
}
}
}
func (n *node) find(chars []rune) []scope {
var scopes []scope
size := len(chars)
cur := n
for i := 0; i < size; i++ {
child, ok := cur.children[chars[i]]
if ok {
cur = child
} else {
for cur != n {
cur = cur.fail
if child, ok = cur.children[chars[i]]; ok {
cur = child
break
}
}
if child == nil {
continue
}
}
for child != n {
if child.end {
scopes = append(scopes, scope{
start: i + 1 - child.depth,
stop: i + 1,
})
}
child = child.fail
}
}
return scopes
}