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
|
struct SuffixTree {
struct Vert {
int start, end, suffix;
map<char, int> next;
};
string s;
int root, lastIdx, needsSuffix, pos, remainder;
int curVert, curEdge, curLen;
// Each Vertex gives its children range as [start, end)
vector<Vert> tree;
SuffixTree(string& s) : s(s) {
needsSuffix = remainder = curEdge = curLen = 0;
lastIdx = pos = -1;
root = curVert = newVert(-1, -1);
for (int i = 0; i < sz(s); i++) extend();
}
int newVert(int start, int end) {
Vert v;
v.start = start;
v.end = end;
v.suffix = 0;
tree.push_back(v);
return ++lastIdx;
}
int len(Vert& v) {
return min(v.end, pos + 1) - v.start;
}
void addSuffixLink(int vert) {
if (needsSuffix) tree[needsSuffix].suffix = vert;
needsSuffix = vert;
}
bool fullImplicitEdge(int vert) {
if (curLen >= len(tree[vert])) {
curEdge += len(tree[vert]);
curLen -= len(tree[vert]);
curVert = vert;
return true;
}
return false;
}
void extend() {
pos++;
needsSuffix = 0;
remainder++;
while (remainder) {
if (curLen == 0) curEdge = pos;
if (!tree[curVert].next.count(s[curEdge])) {
int leaf = newVert(pos, sz(s));
tree[curVert].next[s[curEdge]] = leaf;
addSuffixLink(curVert);
} else {
int nxt = tree[curVert].next[s[curEdge]];
if (fullImplicitEdge(nxt)) continue;
if (s[tree[nxt].start + curLen] == s[pos]) {
curLen++;
addSuffixLink(curVert);
break;
}
int split = newVert(tree[nxt].start,
tree[nxt].start + curLen);
tree[curVert].next[s[curEdge]] = split;
int leaf = newVert(pos, sz(s));
tree[split].next[s[pos]] = leaf;
tree[nxt].start += curLen;
tree[split].next[s[tree[nxt].start]] = nxt;
addSuffixLink(split);
}
remainder--;
if (curVert == root && curLen) {
curLen--;
curEdge = pos - remainder + 1;
} else {
curVert = tree[curVert].suffix ? tree[curVert].suffix
: root;
}}}
};
|
