-
Notifications
You must be signed in to change notification settings - Fork 74
/
suffix_tree_from_array.py
71 lines (61 loc) · 2.69 KB
/
suffix_tree_from_array.py
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
# python3
import sys
def suffix_array_to_suffix_tree(sa, lcp, text):
"""
Build suffix tree of the string text given its suffix array suffix_array
and LCP array lcp_array. Return the tree as a mapping from a node ID
to the list of all outgoing edges of the corresponding node. The edges in
the list must be sorted in the ascending order by the first character of
the edge label. Root must have node ID = 0, and all other node IDs must
be different nonnegative integers. Each edge must be represented by a
tuple (node, start, end), where
* node is the node ID of the ending node of the edge
* start is the starting position (0-based) of the substring of text
corresponding to the edge label
* end is the first position (0-based) after the end of the substring
corresponding to the edge label
For example, if text = "ACACAA$", an edge with label "$" from root to a
node with ID 1 must be represented by a tuple (1, 6, 7). This edge must
be present in the list tree[0] (corresponding to the root node), and it
should be the first edge in the list (because it has the smallest first
character of all edges outgoing from the root).
"""
tree = {}
# Implement this function yourself
return tree
if __name__ == '__main__':
text = sys.stdin.readline().strip()
sa = list(map(int, sys.stdin.readline().strip().split()))
lcp = list(map(int, sys.stdin.readline().strip().split()))
print(text)
# Build the suffix tree and get a mapping from
# suffix tree node ID to the list of outgoing Edges.
tree = suffix_array_to_suffix_tree(sa, lcp, text)
"""
Output the edges of the suffix tree in the required order.
Note that we use here the contract that the root of the tree
will have node ID = 0 and that each vector of outgoing edges
will be sorted by the first character of the corresponding edge label.
The following code avoids recursion to avoid stack overflow issues.
It uses two stacks to convert recursive function to a while loop.
This code is an equivalent of
OutputEdges(tree, 0);
for the following _recursive_ function OutputEdges:
def OutputEdges(tree, node_id):
edges = tree[node_id]
for edge in edges:
print("%d %d" % (edge[1], edge[2]))
OutputEdges(tree, edge[0]);
"""
stack = [(0, 0)]
result_edges = []
while len(stack) > 0:
(node, edge_index) = stack[-1]
stack.pop()
if node not in tree:
continue
edges = tree[node]
if edge_index + 1 < len(edges):
stack.append((node, edge_index + 1))
print("%d %d" % (edges[edge_index][1], edges[edge_index][2]))
stack.append((edges[edge_index][0], 0))