def check_all_words():
    # Read the dictionary of all words
    f = open("words.txt")
    dictionary = set()
    for line in f:
        dictionary.add(line.strip())
    f.close()
    # Add some missing words in dictionary
    dictionary.add("a")
    dictionary.add("i")
    dictionary.add("")

    # Initialize variables tracking the longest reducible word(s)
    # that we have seen.
    bestWords = []
    bestLength = 0

    # Initialize cache of all reducible words we have seen.
    # The cache (memo) enables us to check each word for
    # reducibility at most once.  This makes the program
    # run faster (fewer checks) at the expense of using more
    # memory (words stored in cache).
    memo = {}
    for word in dictionary:
        # For more efficiency, we should check the words
        # sorted by length, so that the first reducible
        # word is also the longest.

        # If the word is shorter than our best, we do not
        # even bother to check it since it cannot be
        # the word we are looking for.
        if len(word) < bestLength:
            continue

        # If this word is reducible, it must be at least
        # as long as our current best.  If it is the same
        # length, we add it to the "bestWords" list.  If
        # it is longer, we clear out "bestWords" and start
        # over, updating "bestLength" at the same time.
        if reducible(word, dictionary, memo):
            if len(word) > bestLength:
                #print("new best word", word)
                bestLength = len(word)
                bestWords = [ word ]
            elif len(word) == bestLength:
                #print("equal best word", word)
                bestWords.append(word)

    # After looking at all words in the dictionary, print out
    # the results we saved.
    print("Longest reducible word has", bestLength, "characters")
    print("They are:")
    for word in bestWords:
        print_trail(word, memo)
        print()

def reducible(word, dictionary, memo):
    """Return whether the given "word" is reducible."""

    # Recursion termination condition: either all the letters
    # have been removed, or we have already seen this word and
    # know that it is reducible.
    if len(word) == 0 or word in memo:
        return True

    # Loop through all possible subwords and check whether any
    # of them is reducible.  Because we only need to find one
    # reducible subword, we can return immediately when we do
    # find one.
    # "memo" is the cache where we store the set of reducible
    # words that we have seen.  When we know that "word" is
    # reducible, we add it into the cache.  Note that we do not
    # need to do so for subwords since it will have been added
    # already by the calls to "reducible" with the subwords.
    for subword in shorten(word):
        if subword not in dictionary:
            continue
        if reducible(subword, dictionary, memo):
            memo[word] = True
            return True
    return False

def shorten(word):
    """Return the set of strings one character shorter than "word"."""

    return set([ word[:i] + word[i + 1:] for i in range(len(word)) ])
    # Above statement is the "list comprehension" version of:
    #
    # words = []
    # for i in range(len(word)):
    #     words.append(word[:i] + word[i + 1:])
    # return set(words)
    #
    # Of course, we can directly create the set:
    #
    # words = set()
    # for i in range(len(word)):
    #     words.add(word[:i] + word[i + 1:])
    # return words

def print_trail(word, memo):
    """Print trail of subwords that make "word" reducible."""

    # Note that "print_trail" is also recursive.
    # We use the memo cache that we built to find a reducible
    # subword and print its trail.

    # Recursion termination condition
    if len(word) == 0:
        return
    print(word, end=' ')
    for subword in shorten(word):
        if subword in memo:
            # Recurse for good subword
            print_trail(subword, memo)
            # We only need one trail, so we can immediately
            # return after printing one.
            return

check_all_words()