Repository navigation
Expand file tree
/
Copy pathUkkonenSuffixTree.java
More file actions
144 lines (141 loc) · 5.29 KB
/
Copy pathUkkonenSuffixTree.java
File metadata and controls
144 lines (141 loc) · 5.29 KB
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
import java.io.*;
class SuffixTreeNode {
public SuffixTreeNode[] descendants;
public int[] left, right;
public SuffixTreeNode suffixLink = null;
public static int cnt = 0; // for printing only;
public int id = 1; // for printing only;
public SuffixTreeNode() {
this(128);
}
public SuffixTreeNode(int sz) {
id = cnt++;
descendants = new SuffixTreeNode[sz];
left = new int[sz];
right = new int[sz];
for (int i = 0; i < sz; i++)
left[i] = -1;
}
}
public class UkkonenSuffixTree {
protected SuffixTreeNode root;
protected int size, offset;
protected String T;
private int Lt = 1;
private boolean endPoint;
public UkkonenSuffixTree() {
this(0,127);
}
public UkkonenSuffixTree(int from, int to) {
size = to - from + 1;
offset = from;
root = new SuffixTreeNode(size);
root.suffixLink = root;
}
public void printTree(int pos) {
System.out.println();
printTree(root,0,0,0,pos);
}
private void printTree(SuffixTreeNode p, int lvl, int lt, int rt, int pos) {
for (int i = 1; i <= lvl; i++)
System.out.print(" ");
if (p != null) { // if a nonleaf;
if (p == root)
System.out.println(p.id);
else if (p.suffixLink != null) // to print in the middle of
System.out.println(T.substring(lt,rt+1) // update;
+ " " + p.id + " " + p.suffixLink.id
+" [" + lt + " " + rt + "]");
else System.out.println(T.substring(lt,pos+1) + " " + p.id);
for (char i = 0; i < size; i++)
if (p.left[i] != -1) // if a tree node;
printTree(p.descendants[i],lvl+1,p.left[i],p.right[i],pos);
}
else System.out.println(T.substring(lt,pos+1) + " [" + lt + " " + rt + "]");
}
SuffixTreeNode testAndSplit(SuffixTreeNode p, int i) {
int Rt = i-1;
if (Lt <= Rt) {
int pos = T.charAt(Lt)-offset;
SuffixTreeNode pp = p.descendants[pos];
int lt = p.left[pos];
int rt = p.right[pos];
if (T.charAt(i) == T.charAt(lt+Rt-Lt+1)) { // if T(lt..rt) is
endPoint = true; // and extension of
return p; // T(Lt..i);
}
else{// insert a new node r between s and ss by splitting
// edge(p,pp) = T(lt..rt) into
// edge(p,r) = T(lt..lt+Rt-Lt) and
// edge(r,pp) = T(lt+Rt-Lt+1..rt);
pos = T.charAt(lt)-offset;
SuffixTreeNode r = p.descendants[pos] = new SuffixTreeNode(size);
p.right[pos] = lt+Rt-Lt;
pos = T.charAt(lt+Rt-Lt+1)-offset;
r.descendants[pos] = pp;
r.left [pos] = lt+Rt-Lt+1;
r.right[pos] = rt;
endPoint = false;
return r;
}
}
else if (p.left[T.charAt(i)-offset] == -1)
endPoint = false;
else endPoint = true;
return p;
}
private SuffixTreeNode findCanonicalNode(SuffixTreeNode p, int Rt) {
if (Rt >= Lt) {
int pos = T.charAt(Lt)-offset;
SuffixTreeNode pp = p.descendants[pos];
int lt = p.left[pos];
int rt = p.right[pos];
while (rt - lt <= Rt - Lt) {
Lt = Lt + rt - lt + 1;
p = pp;
if (Lt <= Rt) {
pos = T.charAt(Lt)-offset;
pp = p.descendants[pos];
lt = p.left[pos];
rt = p.right[pos];
if (p == root)
pp = root;
}
}
}
return p;
}
private SuffixTreeNode update(SuffixTreeNode p, int i) {
SuffixTreeNode prev = null, r = testAndSplit(p,i);
while (!endPoint) {
int pos = T.charAt(i)-offset;
r.left [pos] = i; // add a T(i)-edge to r;
r.right[pos] = T.length()-1;
if (prev != null)
prev.suffixLink = r;
prev = r;
if (p == root)
Lt++;
else p = p.suffixLink;
p = findCanonicalNode(p,i-1);
r = testAndSplit(p,i); // check if not the endpoint;
}
if (prev != null)
prev.suffixLink = p;
return p;
}
public void run(String text) {
T = text;
final int n = T.length(), pos = T.charAt(0)-offset;
SuffixTreeNode canonicalNodeAP = root, canonicalNodeEP;
root.left [pos] = 0;
root.right[pos] = n-1;
for (int i = 1; i < n; i++) {
canonicalNodeEP = update(canonicalNodeAP,i);
// and thus, endpoint = node(canonicalNodeEP,Lt,i);
canonicalNodeAP = findCanonicalNode(canonicalNodeEP,i);
// and so, active point = node(canonicalNodeAP,Lt,i);
printTree(i);
}
}
}