Find longest common substring.

lcsub.py

def longest_common_substring(s1, s2):
  m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
  longest, x_up_to = 0, 0
  for x in range(1, 1 + len(s1)):
    for y in range(1, 1 + len(s2)): # match every char in s2 against every char in s1
      if s1[x - 1] == s2[y - 1]: # record a char match
        m[x][y] = m[x - 1][y - 1] + 1 # char match tally will accumulate if previous char also matched
        if m[x][y] > longest:
          longest = m[x][y]
          x_up_to = x # record char position of last found match
      else:
          m[x][y] = 0
  return s1[x_up_to - longest: x_up_to]

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python3