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
|
from ass2.ukkonen import ukkonen, skip_count, Point, char_is_after, Node
# s1 = "abdabc"
# s2 = "daba"
# s1 = "abaabaaba"
# s2 = "baabaaabaa"
def longest_prefix(root: Node, s1: str, s2: str, suffixes: tuple):
print(s1[suffixes[0]:])
print(s2[suffixes[1]:])
matches = 0
if suffixes[0] == 0:
point = Point(root, s1[0], 1)
else:
point = skip_count(suffixes[0], Point(root), 0)
for i in range(suffixes[1], len(s2) + 1):
print(s2[i], end=" ")
if char_is_after(point, s2[i]):
if point.is_explicit():
point = Point(point.node, s2[i], 1)
else:
point = skip_count(1, point, i)
matches += 1
print("found")
else:
print("not found")
break
return matches
def main():
s1 = "abcdacbdab"
s2 = "dacbdabc"
print(s1)
tree = ukkonen(s1)
tree.print_tree()
result = longest_prefix(tree, s1, s2, (0, 5))
print(result)
if __name__ == "__main__":
main()
|
