KMP Python

浏览数：39 / 时间：2015年06月08日

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