kmp.py

def KMPSearch(pat, txt):
	S = pat +"$"+ txt
	s = _computeLPSArray(S)
	print(s)
	result = []
	for i in range(len(pat)+1,len(txt)-1):
		if s[i] == len(pat):
			result.append(i - 2*len(pat))
	return result

LPS.py

def _computeLPSArray(pat):
	M = len(pat)
	lps = [0] * M
	border = 0
	for i in range(1,M):
		#Kiểm tra ký tự hiện tại pat[i]
		#so sánh nó với ký tự sau khi đường viên hiện tại kết thúc
		while border > 0 and (pat[i] != pat[border]):
			#Lấy đường viền hiện tại dài nhất của đường u hiện tại
			border = lps[border - 1]
		#So sánh ký tự hiện tại và ký tự đường viên
		if pat[border] == pat[i]:
			#cộng giá trị đường viên
			border = border + 1
			
		#khác thì đường viên bằng 0
		else:
			border = 0
		lps[i] = border
	return lps