1 n = T.length
2 m = P.length
3 pi = Compute-Prefix-Function(P)
4 q = 0 // number of characters matched
5 for i = 1 to n // scan the text from left to right
6 while q > 0 and P[q + 1] not equal T[i]
7 q = pi[q] // next character does not match
8 if P[q + 1] == T[i]
9 q = q + 1 // next character matches
10 if q == m // is all of P matched?
11 print "Pattern occurs with shift" i - m
12 q = pi[q] // look for the next match
#
# I believe the above line (line 12) is wrong. I think q should be reset to zero.
1 m = P.length
2 let pi[1..m] be a new array
3 pi[1] = 0
4 k = 0
5 for q = 2 to m
6 while k > 0 and P[k + 1] not equal P[q]
7 k = pi[k]
8 if P[k + 1] == P[q]
9 k = k + 1
10 pi[q] = k
11 return pi