input = String needle, String haystack
m = needle.length()
n = haystack.length()
table = buildTable(needle)
i = m - 1
while i lte n - 1
	k = 0
	keepGoing = true
	while (k lte (m - 1)) and keepGoing
		nc = needle.charAt((m - 1) - k)
		hc = haystack.charAt(i - k)
		if nc != hc then
			keepGoing = false
		endIf
		k = k + 1
	endWhile
	if (k = m) and keepGoing then
		say((i - m) + 1)
		finish
	else
		c = haystack.charAt(i)
		if table.contains(c) = true then
			i = i + table.get(c)
		else
			i = i + m
		endIf
	endIf
endWhile
say("Not found")
finish
function buildTable(String needle)
	initialize table as Dictionary, j as Integer
	m = needle.length()
	while j < m - 1
		initialize c as String, i as Integer
		c = needle.charAt(j)
		i = (m - 1) - j
		call table.put(c, i)
		j = j + 1
	endWhile
	return table
endFunction