Problem:


Problem B: The Sorcerer's Donut 

Your master went to the town for a day. You could have a relaxed day without hearing his
scolding. But he ordered you to make donuts dough by the evening. Loving donuts so much, he
can't live without eating tens of donuts everyday. What a chore for such a beautiful day.

But last week, you overheard a magic spell that your master was using. It was the time to
try. You casted the spell on a broomstick sitting on a corner of the kitchen. With a flash of
lights, the broom sprouted two arms and two legs, and became alive. You ordered him, then he
brought flour from the storage, and started kneading dough. The spell worked, and how fast he
kneaded it!

A few minutes later, there was a tall pile of dough on the kitchen table. That was enough for
the next week. \OK, stop now." You ordered. But he didn't stop. Help! You didn't know the
spell to stop him! Soon the kitchen table was filled with hundreds of pieces of dough, and he
still worked as fast as he could. If you could not stop him now, you would be choked in the
kitchen filled with pieces of dough.

Wait, didn't your master write his spells on his notebooks? You went to his den, and found the
notebook that recorded the spell of cessation.

But it was not the end of the story. The spell written in the notebook is not easily read by
others. He used a plastic model of a donut as a notebook for recording the spell. He split the
surface of the donut-shaped model into square mesh (Figure B.1), and filled with the letters
(Figure B.2). He hid the spell so carefully that the pattern on the surface looked meaningless.
But you knew that he wrote the pattern so that the spell "appears" more than once (see the next
paragraph for the precise conditions). The spell was not necessarily written in the left-to-right
direction, but any of the 8 directions, namely left-to-right, right-to-left, top-down, bottom-up,
and the 4 diagonal directions.

You should be able to find the spell as the longest string that appears more than once. Here,
a string is considered to appear more than once if there are square sequences having the string
on the donut that satisfy the following conditions.

Each square sequence does not overlap itself. (Two square sequences can share some squares.)

The square sequences start from different squares, and/or go to different directions.

	

Figure B.1: The Sorcerer's Donut Before
Filled with Letters, Showing the Mesh and 8
Possible Spell Directions 

Figure B.2: The Sorcerer's Donut After Filled
with Letters

Note that a palindrome (i.e., a string that is the same whether you read it backwards or forwards)
that satisfies the first condition "appears" twice.

The pattern on the donut is given as a matrix of letters as follows.

ABCD
EFGH
IJKL

Note that the surface of the donut has no ends; the top and bottom sides, and the left and right
sides of the pattern are respectively connected. There can be square sequences longer than both
the vertical and horizontal lengths of the pattern. For example, from the letter F in the above
pattern, the strings in the longest non-self-overlapping sequences towards the 8 directions are
as follows.

FGHE
FKDEJCHIBGLA
FJB
FIDGJAHKBELC
FEHG
FALGBIHCJEDK
FBJ
FCLEBKHAJGDI

Please write a program that finds the magic spell before you will be choked with pieces of donuts
dough.

Input

The input is a sequence of datasets. Each dataset begins with a line of two integers h and w,
which denote the size of the pattern, followed by h lines of w uppercase letters from A to Z,
inclusive, which denote the pattern on the donut. You may assume 3 ≤ h ≤ 10 and 3 ≤ w ≤ 20.

The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output the magic spell. If there is more than one longest string of the same
length, the first one in the dictionary order must be the spell. The spell is known to be at least
two letters long. When no spell is found, output 0 (zero).

Sample Input

5 7
RRCABXT
AABMFAB
RROMJAC
APTADAB
YABADAO
3 13
ABCDEFGHIJKLM
XMADAMIMADAMY
ACEGIKMOQSUWY
3 4
DEFG
ACAB
HIJK
3 6
ABCDEF
GHIAKL
MNOPQR
10 19
JFZODYDXMZZPEYTRNCW
XVGHPOKEYNZTQFZJKOD
EYEHHQKHFZOVNRGOOLP
QFZOIHRQMGHPNISHXOC
DRGILJHSQEHHQLYTILL
NCSHQMKHTZZIHRPAUJA
NCCTINCLAUTFJHSZBVK
LPBAUJIUMBVQYKHTZCW
XMYHBVKUGNCWTLLAUID
EYNDCCWLEOODXYUMBVN
0 0

Output for the Sample Input

ABRACADABRA
MADAMIMADAM
ABAC
0
ABCDEFGHIJKLMNOPQRSTUVWXYZHHHHHABCDEFGHIJKLMNOPQRSTUVWXYZ



Sample input:
5 7
RRCABXT
AABMFAB
RROMJAC
APTADAB
YABADAO
3 13
ABCDEFGHIJKLM
XMADAMIMADAMY
ACEGIKMOQSUWY
3 4
DEFG
ACAB
HIJK
3 6
ABCDEF
GHIAKL
MNOPQR
10 19
JFZODYDXMZZPEYTRNCW
XVGHPOKEYNZTQFZJKOD
EYEHHQKHFZOVNRGOOLP
QFZOIHRQMGHPNISHXOC
DRGILJHSQEHHQLYTILL
NCSHQMKHTZZIHRPAUJA
NCCTINCLAUTFJHSZBVK
LPBAUJIUMBVQYKHTZCW
XMYHBVKUGNCWTLLAUID
EYNDCCWLEOODXYUMBVN
0 0


Sample output:
ABRACADABRA
MADAMIMADAM
ABAC
0
ABCDEFGHIJKLMNOPQRSTUVWXYZHHHHHABCDEFGHIJKLMNOPQRSTUVWXYZ

Submission status: Accepted

Solution code:
import sys
Dir = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
def ds(here, didx, lb, ub, field, start, string, spell):
	s = string + field[here[1]][here[0]]
	if s in spell :
		spell[s] -= 1
	else :
		spell[s] = -1
	delta = Dir[didx]
	next = [here[0] + delta[0], here[1]+ delta[1]]
	if next[0] < lb[0]:   next[0] = ub[0]
	elif next[0] > ub[0]: next[0] = lb[0]
	if next[1] < lb[1]:   next[1] = ub[1]
	elif next[1] > ub[1]: next[1] = lb[1]

	if next != start:
		ds(next, didx, lb, ub, field, start, s, spell)

sys.setrecursionlimit(10000)

while 1:
	h,w = map(int,raw_input().split(" "))
	if w == h == 0: break
	lb = (0,0)
	ub = (w-1,h-1)
	spell = dict()
	donut = [[c for c in raw_input()] for _ in range(h)]
	for j in range(h):
		for i in range(w):
			for d in range(8):
				ds([i,j], d, lb, ub, donut, [i,j], "", spell)
	spell_sort = sorted(spell.iteritems(), key = lambda x : (-len(x[0]),x[0],x[1]))
	lenspell = len(spell_sort)
	for i in range(lenspell):
		if len(spell_sort[i][0]) >= 2 and spell_sort[i][1] <= -2:
			print spell_sort[i][0]
			break
	else :
		print 0

Submission status: Accepted

Solution code:
dwh = zip([1,1,0,-1,-1,-1,0,1],[0,1,1,1,0,-1,-1,-1])
while 1:
    H,W = map(int,raw_input().split())
    if H == 0: break
    S = [raw_input() for i in xrange(H)]
    
    ans = ""
    appear = set([])
    for h in xrange(H):
        for w in xrange(W):
            for dw,dh in dwh:
                s = S[h][w]
                iw,ih = w,h
                w = (w+dw+W)%W; h = (h+dh+H)%H
                while (w,h) != (iw,ih):
                    s += S[h][w]
                    if s in appear:
                        if len(s)  > len(ans): ans = s
                        if len(s) == len(ans): ans = min(ans, s)
                    appear.add(s)
                    w = (w+dw+W)%W; h = (h+dh+H)%H
    print ans if len(ans) > 1 else 0

Submission status: Accepted

Solution code:
dd = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
while 1:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    S = [input() for i in range(h)]

    count = {}
    for i in range(h):
        for j in range(w):
            for dx, dy in dd:
                s = S[i][j]
                count[s] = count.get(s, 0) + 1
                x = (j + dx) % w; y = (i + dy) % h
                while x != j or y != i:
                    s += S[y][x]
                    count[s] = count.get(s, 0) + 1
                    x = (x + dx) % w; y = (y + dy) % h
    ans = min(count, key=lambda x: (-len(x)*(count[x]>1), x))
    print(ans*(len(ans)>1)or 0)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    dd = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

    while True:
        h,w = LI()
        if h == 0 and w == 0:
            break

        a = [S() for _ in range(h)]

        rs = set()
        r = ''
        rm = -1

        for i in range(h):
            for j in range(w):
                for di,dj in dd:
                    tr = a[i][j]
                    for k in range(1,401):
                        ni = (i+di*k) % h
                        nj = (j+dj*k) % w
                        if ni == i and nj == j:
                            break
                        c = a[ni][nj]
                        tr += c
                        l = len(tr)
                        if tr in rs and (l > rm or (l==rm and r > tr)):
                            r = tr
                            rm = l
                        rs.add(tr)

        if r == '':
            rr.append(0)
        else:
            rr.append(r)


    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
'''
7 0 1
6   2
5 4 3
'''
dx=[1,0,-1,0,1,-1,1,-1]
dy=[0,1,0,-1,1,1,-1,-1]

while True:
    h,w=map(int,input().split())
    if h==0:
        break
    field=[list(input()) for i in range(h)]
    allword=set()
    answord=set()
    for i in range(h):
        for j in range(w):
            s=field[i][j]
            if s in allword:
                answord.add((len(s),s))
            else:
                allword.add(s)
            for k in range(8):
                used=[[False for _ in range(w)]for _ in range(h)]
                s=field[i][j]
                used[i][j]=True
                while True:
                    i=(i+dy[k])%h
                    j=(j+dx[k])%w
                    if used[i][j]:
                        break
                    s+=field[i][j]
                    if s in allword:
                        answord.add((len(s),s))
                    else:
                        allword.add(s)
    print(sorted(answord,key=lambda x:(-x[0],x[1]))[0][1] if answord and sorted(answord,key=lambda x:(-x[0],x[1]))[0][0]>1 else 0 )

Submission status: Runtime Error

Solution code:

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_diag = self.lengths[0] * self.lengths[1]
        max_i = self.lengths[0]
        max_j = self.lengths[1]
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    print('computing', rows)
    donut = Donut(rows)

    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]



                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates
                    else:
                        break

                    if length >= direction[2]:
                        break

                if len(spell) > len(longest_spell):
                    longest_spell = spell

    return longest_spell


if __name__ == '__main__':
    while True:
        inp_size = input().split()
        num_rows = int(inp_size[0])

        if num_rows == 0:
            break;

        rows = []
        for i in range(int(num_rows)):
            rows.append(input())

        print(compute(rows))

Submission status: Runtime Error

Solution code:

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_diag = self.lengths[0] * self.lengths[1]
        max_i = self.lengths[0]
        max_j = self.lengths[1]
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]



                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates
                    else:
                        break

                    if length >= direction[2]:
                        break

                if len(spell) > len(longest_spell):
                    longest_spell = spell

    return longest_spell


if __name__ == '__main__':
    while True:
        inp_size = input().split()
        num_rows = int(inp_size[0])

        if num_rows == 0:
            break;

        rows = []
        for i in range(int(num_rows)):
            rows.append(input())

        print(compute(rows))

Submission status: Runtime Error

Solution code:

from sys import stdin

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_diag = self.lengths[0] * self.lengths[1]
        max_i = self.lengths[0]
        max_j = self.lengths[1]
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]



                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates
                    else:
                        break

                    if length >= direction[2]:
                        break

                if len(spell) > len(longest_spell):
                    longest_spell = spell

    return longest_spell


if __name__ == '__main__':
    while True:
        inp_size = stdin.readline().split()
        num_rows = int(inp_size[0])

        if num_rows == 0:
            break;

        rows = []
        for i in range(int(num_rows)):
            rows.append(stdin.readline())

        print(compute(rows))

Submission status: Runtime Error

Solution code:

from sys import stdin

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_diag = self.lengths[0] * self.lengths[1]
        max_i = self.lengths[0]
        max_j = self.lengths[1]
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]



                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates
                    else:
                        break

                    if length >= direction[2]:
                        break

                if len(spell) > len(longest_spell):
                    longest_spell = spell

    return longest_spell


while True:
    inp_size = stdin.readline().split()
    num_rows = int(inp_size[0])

    if num_rows == 0:
        break;

    rows = []
    for i in range(int(num_rows)):
        rows.append(stdin.readline())

    print(compute(rows))

Submission status: Runtime Error

Solution code:

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_diag = self.lengths[0] * self.lengths[1]
        max_i = self.lengths[0]
        max_j = self.lengths[1]
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]



                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates
                    else:
                        break

                    if length >= direction[2]:
                        break

                if len(spell) > len(longest_spell):
                    longest_spell = spell

    return longest_spell


while True:
    inp_size = input().split()
    num_rows = int(inp_size[0])

    if num_rows == 0:
        break;

    rows = []
    for i in range(int(num_rows)):
        rows.append(input())

    print(compute(rows))

Submission status: Runtime Error

Solution code:

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_i = self.lengths[0]
        max_j = self.lengths[1]
        max_diag = self.lengths[0] * self.lengths[1] / gcd_recursive(max_i, max_j)
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest = 0
    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]

                # ignore shorter spells
                if direction[2] <= longest:
                    continue

                while length < longest:
                    spell += donut.get_letter([i, j, direction], length)
                    length += 1

                remaining_duplicates = []
                for duplicate in duplicates:
                    a = duplicate[0]
                    b = duplicate[1]
                    d = duplicate[2]
                    match = True
                    for l in range(0, length):
                        if donut.get_letter(duplicate, l) != spell[l]:
                            match = False
                            break

                    if match:
                        remaining_duplicates.append(duplicate)

                duplicates = remaining_duplicates

                # extend spell as long as there is a match
                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates

                        if len(spell) > longest:
                            longest_spell = spell
                            longest = length
                    else:
                        break

                    if length >= direction[2]:
                        break

    return longest_spell


while True:
    inp_size = input().split()
    num_rows = int(inp_size[0])

    if num_rows == 0:
        break;

    rows = []
    for i in range(int(num_rows)):
        rows.append(input())

    found_spell = compute(rows)
    if len(found_spell) == 1:
        print(0)
    else:
        print(found_spell)

Submission status: Runtime Error

Solution code:

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)


def modulo(x, base):
    return (x % base + base) % base


class Donut:
    def __init__(self, letters):
        self.letters = letters
        self.lengths = [len(letters), len(letters[0])]

        max_i = self.lengths[0]
        max_j = self.lengths[1]
        max_diag = self.lengths[0] * self.lengths[1] / gcd_recursive(max_i, max_j)
        self.directions = [
            [-1, -1, max_diag],
            [-1, 0, max_i],
            [-1, 1, max_diag],
            [0, -1, max_j],
            [0, 1, max_j],
            [1, -1, max_diag],
            [1, 0, max_i],
            [1, 1, max_diag]]

    def get_letter(self, start, dist):
        mi = modulo(start[0] + start[2][0]*dist, self.lengths[0])
        mj = modulo(start[1] + start[2][1]*dist, self.lengths[1])
        return self.letters[mi][mj]


def compute(rows):
    donut = Donut(rows)

    longest = 0
    longest_spell = ''
    for i in range(0, donut.lengths[0]):
        for j in range(0, donut.lengths[1]):
            for direction in donut.directions:
                length = 0
                spell = ''
                duplicates = [[a, b, d]
                              for a in range(donut.lengths[0])
                              for b in range(donut.lengths[1])
                              for d in donut.directions]

                # ignore shorter spells
                if direction[2] <= longest:
                    continue

                while length < longest:
                    spell += donut.get_letter([i, j, direction], length)
                    length += 1

                remaining_duplicates = []
                for duplicate in duplicates:
                    a = duplicate[0]
                    b = duplicate[1]
                    d = duplicate[2]
                    match = True
                    for l in range(0, length):
                        if donut.get_letter(duplicate, l) != spell[l]:
                            match = False
                            break

                    if match:
                        remaining_duplicates.append(duplicate)

                duplicates = remaining_duplicates

                # extend spell as long as there is a match
                while True:
                    letter = donut.get_letter([i, j, direction], length)
                    remaining_duplicates = []
                    for duplicate in duplicates:
                        a = duplicate[0]
                        b = duplicate[1]
                        d = duplicate[2]
                        if donut.get_letter(duplicate, length) == letter:
                            remaining_duplicates.append(duplicate)

                    if len(remaining_duplicates) > 1:
                        length += 1
                        spell += letter
                        duplicates = remaining_duplicates

                        if len(spell) > longest:
                            longest_spell = spell
                            longest = length
                    else:
                        break

                    if length >= direction[2]:
                        break

    return longest_spell


while True:
    inp_size = [input(), input()]
    num_rows = int(inp_size[0])

    if num_rows == 0:
        break;

    rows = []
    for i in range(int(num_rows)):
        rows.append(input())

    found_spell = compute(rows)
    if len(found_spell) == 1:
        print(0)
    else:
        print(found_spell)