input = String needle, String haystack
m = needle.length()
n = haystack.length()
i = 0
j = 0
nextTable = createNext(needle)
while i < n
	if needle.charAt(j) = haystack.charAt(i) then
		if j = (m - 1)	then
			say("The needle is found at ".concat(i - m + 1))
			finish
		endIf
		i = i + 1
		j = j + 1
	else
		j = nextTable.get(j)
		if j = 0 then
			if needle.charAt(j) != haystack.charAt(0) then
				i = i + 1
			endIf
		endIf		
	endIf
endWhile
say("The needle was not found.")
finish
function createNext(String needle)
	initialize nextTable as List
	call nextTable.set(0, 0)
	call nextTable.set(1, 0)
	i = 2
	j = 0
	m = needle.length()
	while i < m
		if needle.charAt(j) = needle.charAt(i - 1) then
			call nextTable.set(i, j + 1)
			i = i + 1
			j = j + 1
		else
			if j > 0 then
				j = nextTable.get(j - 1)
			else
				call nextTable.set(i, 0)
				i = i + 1
			endIf
		endIf
	endWhile
	return nextTable
endFunction