SHARE
TWEET

Untitled

a guest May 24th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # python3
  2. import sys
  3.  
  4. sys.setrecursionlimit(10000)
  5.  
  6.  
  7. class SuffixTree:
  8.     class Node:
  9.         def __init__(self, label):
  10.             self.label = label
  11.             self.out = {}
  12.  
  13.     def __init__(self, text):
  14.         self.root = self.Node(None)
  15.         self.root.out[text[0]] = self.Node(text)
  16.         for i in range(1, len(text)):
  17.             current = self.root
  18.             j = i
  19.             while j < len(text):
  20.                 if text[j] in current.out:
  21.                     child = current.out[text[j]]
  22.                     label = child.label
  23.                     k = j + 1
  24.                     while k - j < len(label) and text[k] == label[k - j]:
  25.                         k += 1
  26.                     if k - j == len(label):
  27.                         current = child
  28.                         j = k
  29.                     else:
  30.                         cExist, cNew = label[k - j], text[k]
  31.                         mid = self.Node(label[:k - j])
  32.                         mid.out[cNew] = self.Node(text[k:])
  33.                         mid.out[cExist] = child
  34.                         child.label = label[k - j:]
  35.                         current.out[text[j]] = mid
  36.                 else:
  37.                     current.out[text[j]] = self.Node(text[j:])
  38.  
  39.  
  40. def build_suffix_tree(text):
  41.     tree = SuffixTree(text)
  42.     return tree
  43.  
  44.  
  45. def print_out(node):
  46.     for child in node.out:
  47.         print(node.out[child].label)
  48.         print_out(node.out[child])
  49.  
  50.  
  51. if __name__ == '__main__':
  52.     text = sys.stdin.readline().strip()
  53.     result = build_suffix_tree(text)
  54.     print_out(result.root)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top