-
Notifications
You must be signed in to change notification settings - Fork 8
/
SuffixTree
66 lines (62 loc) · 1.82 KB
/
SuffixTree
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
function insert(T, string, start_index, length){
i = start_index
while(i < length)
if T.arr[string[i]]) is NULL
T.arr[string[i]] = new node()
T = T.arr[string[i]]
while(i < length)
T.label = T.label+string[i]
i = i+1
endwhile
return
endif
j=0, x=i
temp = T.arr[string[i]]
while j < temp.label.length and i < length && temp.label[j] = string[i]
i = i+1
j = j+1
endwhile
if i = length
return
endif
if j = temp.label.length
cnt = 0
for k = 'a' to 'z'
if temp.arr[k] = NULL
cnt = cnt+1
endif
endfor
if cnt = 27
while i < length
temp.label = temp.label + string[i]
i = i+1
endwhile
else
T = temp
endifelse
else
newInternalNode = new node()
k=0
while k < j
newInternalNode.label = newInternalNode.label + temp.label[k]
k = k+1
endwhile
newInternalNode.arr[string[j]] = new node()
while k < temp.label.length
newInternalNode.arr[string[j]].label+=temp.label[k]
k = k+1
endwhile
for k = 'a' to 'z'
newInternalNode.arr[string[j]].arr[k] = temp.arr[k]
endfor
T.arr[string[x]] = newInternalNode
T = T.arr[string[x]]
endifelse
endwhile
}
function makeSuffixTree(string, length){
Trie T
string = concatenate(string, "{")
for i = 0 to length
insertInTrie(T, string, i, length)
}