a naïve longest common substring impl

lcs.py

def static_lcs(one,two):
    lcs, candidate = '', ''
    for o,t in zip(one, two):
        if o == t:
            candidate = candidate + o
            if len(candidate) > len(lcs):
                lcs = candidate
        else:
            candidate = ''
    return lcs

def lcs(one,two):
    lcs, candidate = '', ''
    for i,c in enumerate(one):
        if i == 0:
            continue
        first, second = one[-i:], two[:i]
        #print '\n\n%s\n%s' % (first, second)
        candidate = static_lcs(first, second)
        if len(candidate) > len(lcs):
            lcs = candidate
    for i,c in enumerate(two):
        i = len(two) - i
        first, second = two[-i:], one[:i]
        #print '\n\n%s\n%s' % (first, second)
        candidate = static_lcs(first, second)
        if len(candidate) > len(lcs):
            lcs = candidate
    return lcs


def lcs(one,two):
    lcs, candidates, eone = '', [], enumerate(one)
    eone.next()
    for i,c in eone:
        candidates.append(static_lcs(one[-i:], two[:i]))
    for i,c in enumerate(two):
        candidates.append(static_lcs(two[-len(two)+i:], one[:len(two)-i]))
    return max(candidates, key=len)

def lcs(one,two):
    def i():
        for i,c in enumerate(one):
            if i > 0:
                yield static_lcs(one[-i:], two[:i])
        for i,c in enumerate(two):
            yield static_lcs(two[-len(two)+i:], one[:len(two)-i])
    return max(i(), key=len)

from itertools import chain
lcs = lambda one,two: max(chain(
        (static_lcs(one[-i:], two[:i]) for i,c in enumerate(one) if i > 0),
        (static_lcs(two[-len(two)+i:], one[:len(two)-i]) for i,c in enumerate(two))
    ), key=len)