blob: 78cf6c4633b982f2191b25fc8c2377ca2659f9aa (
plain)
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
|
from ass2.ukkonen import Node, ukkonen
import sys
def depth_first_apply(node: Node, func):
"""
Apply a given function to every leaf node in the suffix tree via DFS
"""
if not node.children:
func(node.suffix_index)
else:
for child in node.children.ordered_items():
depth_first_apply(child, func)
def read_in_string(filename):
"""
Reads in a string from a given file name
"""
with open(filename, "r") as file:
return file.read()
def suffix_array(string):
"""
Generates a suffix array from a given string using Ukkonen's and a depth first search
"""
tree = ukkonen(string)
buffer = []
depth_first_apply(tree, buffer.append)
return buffer
def write_suffix_array(string, filename):
"""
Writes a suffix array for a given string to a given file name.
"""
with open(filename, "w") as file:
buffer = suffix_array(string)
file.write("\n".join(map(str, buffer)))
def main():
assert len(sys.argv) == 2
string = read_in_string(sys.argv[1])
write_suffix_array(string, "output_suffix_array.txt")
if __name__ == "__main__":
main()
|
