KMP-Matcher

KMP-Matcher (T, P)

The above procedure computes whether the given pattern P is present in the text string T or not. It uses auxiliary function ‘compute-prefix’ to compute Pf.
Step 1 Initialization
set n  length [T]
set m  length [P]
Calling Compute-Prefix
set Pf  Compute-prefix (P).
Numbers of characters matched
set q  0
Step 3 loop, scanning from left to right along text
for i  1 to n
while (q > 0 and P [q + 1]  T [i] )
set q  Pf [q]
no matching of next character
i f (P [q + 1] = T [i]) then
set q  q + 1
matching of next character
if (q = m) then
whether all character of P matched ?
display : “pattern occur with shift” i – m.
set q  Pf [q]
look for next match