KMP Python

KMP is an advanced algorithm for search an substring in a string.

It mains definite finite states.

The general worst time complexity is O(n), because we need to search the whole string.

code is as follow?

def kmp(pat):
	M = len(pat)
	#R = len(set(pat))
	table = {}
	i = 0
	for char in pat:
		if char not in table:
			table[char] = i
			i += 1
	R = len(table)
	#print table
	dfa = [[0 for j in range(M)] for  i in range(R)]
	dfa[table[pat[0]]][0] = 1
	last = 0
	for j in xrange(1, M):
	 	for c in range(R):
	 		dfa[c][j] = dfa[c][last] ## copy mismatch
	 	dfa[table[pat[j]]][j] = j + 1 ## update new state
	 	last = dfa[table[pat[j]]][last] ## preserve last state
	return dfa, table

def search(txt, pat):
	n = len(txt)
	m = len(pat)
	dfa, table = kmp(pat)
	j = 0
	for i in range(n):
		if txt[i] in table:
			j = dfa[table[txt[i]]][j]
	if j == len(pat):
		return True
	return False



pat = "ABAB"
txt = "ABCAB"
search(txt, pat)

KMP Python

原文：http://blog.csdn.net/hyperbolechi/article/details/44613763