knuth morris pratt algorithm

kmp.py

#! /usr/bin/env python

# Description: Knuth-Morris-Pratt algorithm

__author__ = 'Jay <[email protected]>'

def prefix_table(p):
    m = len(p)
    pi = [0] * m
    k = 0
    for q in range(1, m):
        while k > 0 and p[k] != p[q]:
            k = pi[k - 1]
        if p[k] == p[q]:
            k = k + 1
        pi[q] = k
    return pi

def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = prefix_table(p)
    q = 0
    for i in range(n):
        while q > 0 and p[q] != t[i]:
            q = pi[q - 1]
        if p[q] == t[i]:
            q = q + 1
        if q == m:
            return i - m + 1
    return -1

I don't supposed you could modify this slightly to show each instance, and not just one, could you?