Longest common substring between two strings

lcs.py

def longest_common_substring(s1, s2):
    """
    lcs[i,j] = if match lcs[i-1, j-1] + 1
    lcs[i,j] = if not match 0
    """
    m = len(s1)
    n = len(s2)

    # Hash table not be more memory efficient. Here we have n*m
    # entries guaranteed. In a hash table all entries that are 0
    # we wouldn't have to deal with.
    table = [[0 for j in xrange(n)] for i in xrange(m)]

    best = 0
    indices = (0,0)

    for i in xrange(m):
        for j in xrange(n):
            # corner cases where we have nothing behind us
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    table[i][j] = 1
                else:
                    table[i][j] = table[i-1][j-1] + 1
            else:
                table[i][j] = 0

            if table[i][j] > best:
                best = table[i][j]
                indices = (i, j)

    return s1[indices[0]-best+1:indices[0]+1]
                


longest_common_substring("mr hello w", "ok sirello world") # "ello w"