-
Notifications
You must be signed in to change notification settings - Fork 4
/
lcss_test.go
243 lines (231 loc) · 9.9 KB
/
lcss_test.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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
package lcss
import (
"testing"
"github.com/stretchr/testify/assert"
)
func TestCharNodeAdd(t *testing.T) {
node := &charNode{}
node.Add([]byte("abc"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 1, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 1)
assert.Equal(t, byte('c'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
node.Add([]byte{})
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
node.Add([]byte("abd"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 2, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 2, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 2)
assert.Equal(t, byte('c'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
assert.Equal(t, byte('d'), node.children[0].children[0].children[1].char)
assert.Equal(t, 1, node.children[0].children[0].children[1].used)
assert.Len(t, node.children[0].children[0].children[1].children, 0)
node.Add([]byte("abc"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 3, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 3, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 2)
assert.Equal(t, byte('c'), node.children[0].children[0].children[0].char)
assert.Equal(t, 2, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
assert.Equal(t, byte('d'), node.children[0].children[0].children[1].char)
assert.Equal(t, 1, node.children[0].children[0].children[1].used)
assert.Len(t, node.children[0].children[0].children[1].children, 0)
}
func TestCharNodeRemove(t *testing.T) {
node := &charNode{}
node.Add([]byte("abc"))
node.Remove([]byte("abc"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 0)
node.Add([]byte("abc"))
node.Add([]byte("abd"))
node.Remove([]byte("abc"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 1, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 1)
assert.Equal(t, byte('d'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
node.Remove([]byte{})
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 1, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 1)
assert.Equal(t, byte('d'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
node.Add([]byte("ab"))
node.Remove([]byte("ab"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 1, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 1)
assert.Equal(t, byte('d'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 0)
node.Add([]byte("ab"))
node.Remove([]byte("abd"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 1, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 0)
}
func TestCharNodeLongestCommonPrefixLength(t *testing.T) {
node := &charNode{}
assert.Equal(t, 0, node.LongestCommonPrefixLength())
node.Add([]byte("abc"))
assert.Equal(t, 3, node.LongestCommonPrefixLength())
node.Add([]byte("abd"))
assert.Equal(t, 2, node.LongestCommonPrefixLength())
node.Remove([]byte("abd"))
assert.Equal(t, 3, node.LongestCommonPrefixLength())
node.Add([]byte("ab"))
assert.Equal(t, 2, node.LongestCommonPrefixLength())
}
func TestCharNodeLongestCommonPrefix(t *testing.T) {
node := &charNode{}
assert.Equal(t, []byte{}, node.LongestCommonPrefix())
node.Add([]byte("abc"))
assert.Equal(t, []byte("abc"), node.LongestCommonPrefix())
node.Add([]byte("abd"))
assert.Equal(t, []byte("ab"), node.LongestCommonPrefix())
node.Remove([]byte("abd"))
assert.Equal(t, []byte("abc"), node.LongestCommonPrefix())
node.Add([]byte("ab"))
assert.Equal(t, []byte("ab"), node.LongestCommonPrefix())
}
func TestCharNodeBug1(t *testing.T) {
node := &charNode{}
node.Add([]byte("a"))
node.Add([]byte("a"))
node.Remove([]byte("a"))
node.Add([]byte("abbara"))
node.Add([]byte("abr"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('a'), node.children[0].char)
assert.Equal(t, 3, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('b'), node.children[0].children[0].char)
assert.Equal(t, 2, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 2)
assert.Equal(t, byte('b'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 1)
assert.Equal(t, byte('r'), node.children[0].children[0].children[1].char)
assert.Equal(t, 1, node.children[0].children[0].children[1].used)
assert.Len(t, node.children[0].children[0].children[1].children, 0)
assert.Equal(t, 1, node.LongestCommonPrefixLength())
assert.Equal(t, []byte("a"), node.LongestCommonPrefix())
}
func TestCharNodeBug2(t *testing.T) {
node := &charNode{}
node.Add([]byte("habrahabr"))
node.Add([]byte("bbara"))
node.Add([]byte("mraja"))
node.Remove([]byte("habrahabr"))
node.Add([]byte("r"))
node.Remove([]byte("bbara"))
node.Add([]byte("ra"))
node.Remove([]byte("r"))
node.Add([]byte("rahabr"))
node.Remove([]byte("bbara"))
node.Add([]byte("ra"))
node.Remove([]byte("mraja"))
node.Add([]byte("raja"))
assert.Equal(t, byte(0), node.char)
assert.Equal(t, 0, node.used)
assert.Len(t, node.children, 1)
assert.Equal(t, byte('r'), node.children[0].char)
assert.Equal(t, 3, node.children[0].used)
assert.Len(t, node.children[0].children, 1)
assert.Equal(t, byte('a'), node.children[0].children[0].char)
assert.Equal(t, 3, node.children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children, 2)
assert.Equal(t, byte('h'), node.children[0].children[0].children[0].char)
assert.Equal(t, 1, node.children[0].children[0].children[0].used)
assert.Len(t, node.children[0].children[0].children[0].children, 1)
assert.Equal(t, byte('j'), node.children[0].children[0].children[1].char)
assert.Equal(t, 1, node.children[0].children[0].children[1].used)
assert.Len(t, node.children[0].children[0].children[1].children, 1)
assert.Equal(t, []byte("ra"), node.LongestCommonPrefix())
}
func TestLongestCommonSubstring(t *testing.T) {
assert.Equal(t, []byte{}, LongestCommonSubstring())
assert.Equal(t, []byte("abc"), LongestCommonSubstring([]byte("abc")))
assert.Equal(t, []byte{}, LongestCommonSubstring([]byte("abc"), []byte{}))
assert.Equal(t, []byte("ab"), LongestCommonSubstring([]byte("abc"), []byte("abd")))
assert.Equal(t, []byte("bc"), LongestCommonSubstring([]byte("abc"), []byte("dbc")))
assert.Equal(t, []byte("ab"), LongestCommonSubstring([]byte("ab"), []byte("abd")))
assert.Equal(t, []byte("ABC"), LongestCommonSubstring(
[]byte("ABABC"), []byte("BABCA"), []byte("ABCBA")))
assert.Equal(t, []byte("ra"), LongestCommonSubstring(
[]byte("habrahabr"),
[]byte("abbara"),
[]byte("humraja")))
assert.Equal(t, []byte("abcdez"), LongestCommonSubstring(
[]byte("zxabcdezy"),
[]byte("yzabcdezx"),
[]byte("abcdez"),
[]byte("zyzxabcdez")))
}
func TestLongestCommonSubstringWithSuffixArrays(t *testing.T) {
assert.Panics(t, func() {
LongestCommonSubstringWithSuffixArrays([][]byte{[]byte("abc")}, [][]int{})
})
assert.Panics(t, func() {
LongestCommonSubstringWithSuffixArrays(
[][]byte{[]byte("abc"), []byte("cba")},
[][]int{{1, 2}, {1, 2, 3}})
})
assert.Equal(t, []byte{}, LongestCommonSubstringWithSuffixArrays(nil, nil))
assert.Equal(t, []byte("abc"), LongestCommonSubstringWithSuffixArrays(
[][]byte{[]byte("abc")}, [][]int{{1, 2, 3}}))
}