input = String needle
initialize f as Dictionary, s as Dictionary
m = needle.length()
i = m
j = m + 1
call f.put(i, j)
while i > 0
	while (j lte m) and (needle.charAt(i - 1) != needle.charAt(j - 1))
		if s.get(j) = 0 then
			call s.put(j, (j - i))
		endIf
		j = f.get(j)
	endWhile
	i = i - 1
	j = j - 1
	call f.put(i, j)
endWhile