KMP的python实现代码,Python代码库,德仔网

代码语言

代码分类

【Python】 KMP的python实现

作者:daleshen128 / 发布于2013/3/18/ 1132

KMP算法的精髓在于，在匹配不一致的时候，根据模式中前缀和后缀的重合状况，做适度的回溯。而不是像普通的字符串搜索操作的那样，完全回退。


	#!/usr/bin/python

	def getNext(pattern, next):
	 j = 0
	 plen = len(pattern)
	 next.append(0)
	 for i in range(1, plen):
	 while ((j > 0) and (pattern[j] != pattern[i])):
	 j = next[j-1]
	 if (pattern[i] == pattern[j]):
	 j = j + 1
	 next.append(j)
	


	def kmp_search(text, pattern, next):
	 j = 0;
	 plen = len(pattern)
	 tlen = len(text)

	 for i in range(0, tlen):
	 while j > 0 and text[i] != pattern[j]:
	 j = next[j-1]

	 if text[i] == pattern[j] :
	 j = j + 1;

	 if j == plen :
	 print "from ", i-j+1, "to ", i
	 j = next[j-1]


	text = ("aaaaaaaaaaaaaaaaaaaab")
	pattern = ("aaab")
	next = []

	text1 = ("abababababababababa")
	pattern1 = ("ababab")
	next1 = []

	getNext(pattern, next)
	print next
	kmp_search(text, pattern, next)
	print text
	print pattern

	getNext(pattern1, next1)
	print next1
	kmp_search(text1, pattern1, next1)
	print text1
	print pattern1

试试其它关键字

　python　

同语言下

可能有用的

daleshen128贡献的其它代码(3)