Find the longest common substring between two strings.

gistfile1.py

from collections import defaultdict

def longest_common_substring(a, b):
  index = defaultdict(list)
  for i, c in enumerate(b):
    index[c].append(i)
  mxi, mxj, mxsz = 0, 0, 0
  matches = defaultdict(int)
  for i, c in enumerate(a):
    new_matches = defaultdict(int)
    for j in index[c]:
      k = new_matches[j] = matches[j - 1] + 1
      if k > mxsz:
        mxi, mxj, mxsz = i, j, k
    matches = new_matches
  return mxi - mxsz + 1, mxj - mxsz + 1, mxsz