Knuth Morris Pratt String Matching Algorithm

kmp.py

def prefix_table(pattern):
	result = [0]
	for i in range(1,len(pattern)):
		val = 0
		for j in range(i,0,-1):
			prefix = pattern[0:j]#Generate a prefix
			suffix = pattern[i-j+1:i+1]#Generate a suffix
			if prefix == suffix:
				val = len(prefix)
				break
		result.append(val)
	return result

def kmp_search(text,pattern):
    
    table = prefix_table(pattern)
    # Walk through text string
    j = 0  # Number of chars matched in pattern
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = table[j - 1]  # Fall back in the pattern
        if text[i] == pattern[j]:
            j += 1  # Next char matched, increment position
            if j == len(pattern):
                print "Pattern found at index",i - (j - 1)
    
    
kmp_search("abacaabacab","abacab")