solve.py

import sys
import pickle
from collections import defaultdict


def tree():
    return defaultdict(tree)


class Trie(object):
    def __init__(self):
        self.root = tree()

    def add(self, word):
        node = self.root
        for cp in word:
            node = node[cp]


def is_partial_match(trie, word):
    node = trie.root
    for idx, cp in enumerate(word):
        if cp not in node:
            return idx
        node = node[cp]
    return idx

try:
    with open("words.trie.pickle", "rb") as cachefile:
        word_trie = pickle.load(cachefile)
except:
    word_trie = Trie()
    with open("/usr/share/dict/words", "r") as words:
        for word in words.readlines():
            word_trie.add(word)
    with open("words.trie.picke", "wb+") as cachefile:
        pickle.dump(word_trie, cachefile)

for line in sys.stdin.readlines():
    line = line.strip()
    match = is_partial_match(word_trie, line) + 1
    print(''.join((line[:match], "<", line[match:])))