Rabin-karp-Match

Rabin-karp-Match (T, P, d, q)

The above procedure finds the pattern string P in the given text string T. The variable ‘d’ indicates the radix, and ‘q’ is some prime.
Step 1 Initialization
set n  length [T]
set m  length [P]
set h  dm– 1 mod q.
set P  0, to  0.
Step 2 Preprocessing of the string, loop
for i  1 to m
set P  (dp + P [i] ) mod q.
set to  (dto + T [i] ) mod q.
Step 3 Matching the pattern string
for S  0 to n – m
if (P = ts) then
if (P [1..m]  T[S + 1.... S + m] then
display : “occurrence of pattern with shift”
if ( S < n – m) then
set ts + 1  (d (ts – T [S + 1] h) + T [S + m + 1] ) mod q.
Step 4 return at the point of call.
return