decode.py

LETTERS = "abcdefghijklmnopqrstuvwxyz"

def prepare(line, subst):
    result = []
    for word in line.split():
        out = []
        for c in word:
            out.append(subst[c] if c in subst else LETTERS)
        result.append(out)
    return result


def combine(data):
    for i in data[0]:
        if len(data) > 1:
            for j in combine(data[1:]):
                yield i+j
        else:
            yield i


def decode(line, dic, subst):
    result = []
    data = prepare(line, subst)
    for encoded in data:
        for word in combine(encoded):
            if word in dic:
                result.append(word)
                break
    return ' '.join(result)


if __name__ == '__main__':
    import sys
    
    encrypted = next(sys.stdin)
    dictionary = next(sys.stdin)
    subst = {}
    for line in sys.stdin:
        x = line.split()
        subst[x[0]] = ''.join(x[1:])

    print(decode(encrypted, dictionary, subst))