Pattern Search

NHAY.py

flag = 1
def calcLPS(pat):
	leng = 0
	i = 1
	lps = [0]*len(pat)

	while i<len(pat):
		print pat[i],i+1,pat[leng],leng+1
		if pat[i]==pat[leng]:
			leng+=1
			lps[i] = leng
			i+=1
		else:
			if leng:
				leng = lps[leng-1]
			else:
				lps[i] = 0
				i+=1
	return lps

def KMP(txt,pat):
	M = len(pat)
	N = len(txt)
	j = 0

	lps = calcLPS(pat)
	print lps
	i = 0
	while i<N:
		if pat[j] == txt[i]:
			# print pat[j],j,txt[i],i
			i+=1
			j+=1

		if j==M:
			print i-j
			flag = 0
			j = lps[j-1]
		elif i<N and pat[j] != txt[i]:
			if j:
				j = lps[j-1]
			else:
				i+=1

def main():
	try:
		while True:
			if not int(raw_input()):
				break

			text = raw_input()
			pat = raw_input()

			KMP(pat,text)
			if flag:
				print ""
	except EOFError:
		pass
main()