kmp search

gistfile1.py

"""
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
"""
def kmp_make_table(word):
    table = len(word) * [0]
    pos = 2
    cnd = 0

    table[0] = -1
    table[1] = 0

    while pos < len(word):
        if word[pos - 1] == word[cnd]:
            cnd += 1
            table[pos] = cnd
            pos += 1
        elif cnd > 0:
            cnd = table[cnd]
        else:
            table[pos] = 0
            pos += 1

    return table

def kmp_search(text, pattern):
    t = kmp_make_table(pattern)

    m = 0
    i = 0

    while m+i < len(text):
        if pattern[i] == text[m+i]:
            if i == len(pattern) - 1:
                return m
            i += 1
        else:
            m = m + i - t[i]
            if t[i] > -1:
                i = t[i]
            else:
                i = 0

    return -1