#!/usr/bin/python3 # # this program reads a set of words from the standard input, then it # inserts them into a ternary search trie (TST) and then prints the # TST # # For example, with this input: # # lugano # ciao # lunatic # cappero # algorithms # algo # altro # altrove # allegro # ciaa # math # matrix # # the output should be: # # /a=l=g=o*r=i=t=h=m=s* # / \ /l=e=g=r=o* # / \t=r=o*v=e* # / /a=p=p=e=r=o* # / / /a* # /c=i=a=o* # l=u=g=a=n=o* # \ \n=a=t=i=c* # \m=a=t=h* # \r=i=x* # import sys class TSTNode: """represents a node in a ternary search trie""" def __init__(self,c): self.c = c self.is_key = False self.equal = None self.left = None self.right = None def tst_chain(k, pos): prev = None res = None for i in range(pos, len(k)): n = TSTNode(k[i]) if prev != None: prev.equal = n prev = n if res == None: res = n n.is_key = True return res def tst_insert(t,k): if t == None: return tst_chain(k,0) root = t i = 0 while True: if k[i] > t.c: if t.right == None: t.right = tst_chain(k,i) return root else: t = t.right elif k[i] < t.c: if t.left == None: t.left = tst_chain(k,i) return root else: t = t.left else: if i >= len(k)-1: t.is_key = True return root if t.equal == None: t.equal = tst_chain(k,i+1) return root else: i = i + 1 t = t.equal def tst_add_from_file(t,f): for l in f: k = l.strip() if k != '': t = tst_insert(t, k) return t def tst_print_left(prefix,t): if t == None: return if t.left != None: prefix = prefix + ' /' tst_print(prefix, t.left) else: prefix = prefix + ' ' if t.equal != None: tst_print_left(prefix, t.equal) def tst_print_equal_right(prefix,t): if t == None: return sys.stdout.write(t.c) if (t.is_key): sys.stdout.write('*') else: sys.stdout.write('=') if t.right != None: prefix = prefix + ' \\' else: prefix = prefix + ' ' if t.equal != None: tst_print_equal_right(prefix, t.equal) else: sys.stdout.write('\n') if t.right != None: tst_print(prefix, t.right) def tst_print(prefix, t): if t == None: return if len(prefix) > 1 and prefix[-1:] == '/': tst_print_left(prefix[:-1]+' ',t) else: tst_print_left(prefix,t) sys.stdout.write(prefix) if len(prefix) > 1 and prefix[-1:] == '\\': tst_print_equal_right(prefix[:-1]+' ',t) else: tst_print_equal_right(prefix,t) T = None T = tst_add_from_file(T, sys.stdin) tst_print('',T)