board = '''
m	a	i	n	v	f
a	n	a	f	d	d
s	m	i	t	h	a
i	r	o	n	r	v
e	m	o	z	a	i
a	e	e	t	a	d
'''

words = '''
ezra
david
sam
smith
iron
fire
'''

# use this to get a dictionary involved.
#words = open('dictionary.txt', 'rt').read()

BOARD = {}

x = 0
y = 0
for line in board.strip().split('\n'):
    y += 1
    x = 0
    for char in line:
        char = char.lower()
        if char in 'abcdefghijklmnopqrstuvwxyz':
            x += 1
            BOARD[x,y] = char

WORDS = set()

for line in words.strip().split('\n'):
    word = line.strip().lower()
    if len(word) >= 3:
        WORDS.add(word)

DIREC = (
    (0,-1),
    (1,-1),
    (1,0),
    (1,1),
    (0,1),
    (-1,1),
    (-1,0),
    (-1,-1),
    )

PREFX = set()

FOUND = set()

for word in WORDS:
    prefix = ''
    for c in word[:-1]:
        prefix += c
        PREFX.add(prefix)

# For each position on the board
for x,y in BOARD:

    # For each direction of 8
    for xx,yy in DIREC:
        x1 = x  #cur pos
        y1 = y  #cur pos
        word = '' #cur word

        while True:

            # Check if off board
            if (x1,y1) not in BOARD:
                break

            # Get character at current pos
            word += BOARD[x1,y1]

            # If it is a word, add it
            if word in WORDS:
                FOUND.add(word)

            # If this is not a prefix, then bail out
            if word not in PREFX:
                break

            # Increment current position based on direction
            x1 += xx
            y1 += yy

print(FOUND)