Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # python3
- import sys
- sys.setrecursionlimit(10000)
- class SuffixTree:
- class Node:
- def __init__(self, label):
- self.label = label
- self.out = {}
- def __init__(self, text):
- self.root = self.Node(None)
- self.root.out[text[0]] = self.Node(text)
- for i in range(1, len(text)):
- current = self.root
- j = i
- while j < len(text):
- if text[j] in current.out:
- child = current.out[text[j]]
- label = child.label
- k = j + 1
- while k - j < len(label) and text[k] == label[k - j]:
- k += 1
- if k - j == len(label):
- current = child
- j = k
- else:
- cExist, cNew = label[k - j], text[k]
- mid = self.Node(label[:k - j])
- mid.out[cNew] = self.Node(text[k:])
- mid.out[cExist] = child
- child.label = label[k - j:]
- current.out[text[j]] = mid
- else:
- current.out[text[j]] = self.Node(text[j:])
- def build_suffix_tree(text):
- tree = SuffixTree(text)
- return tree
- def print_out(node):
- for child in node.out:
- print(node.out[child].label)
- print_out(node.out[child])
- if __name__ == '__main__':
- text = sys.stdin.readline().strip()
- result = build_suffix_tree(text)
- print_out(result.root)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement