Python - KMP算法

def kmp_match(tex, pat):

	n = len(tex)

	m = len(pat)

	tex = '0' + tex

	pat = '0' + pat

	pi = []

	pi.append(0)

	pi.append(0)

	p = 0

	for i in range(2, m + 1):

		while (p) and (pat[p + 1] != pat[i]):

			p = pi[p]

		if (pat[p + 1] == pat[i]):

			p = p + 1

		pi.append(p)

	p = 0

	for i in range(1, n + 1):

		while (p) and (pat[p + 1] != tex[i]):

			p = pi[p]

		if (pat[p + 1] == tex[i]):

			p = p + 1

		if (p == m):

			print i - m + 1

			p = pi[p]

tex = 'abbababbabbaaabaabb'

pat = 'aab'

kmp_match(tex, pat)