Substring matching

Find if string P in T?


Rabin-Karp algorithm
Hashing P and each substring of T
compare hash value to examine
Trick: Hashing substring of T can be reduced to 1 step

Pseudo code:
Rabin-Karp-matcher(T,P,d,q)
n= length(P)
m=length(T)

h= d^(m-1) mod q
p=0
t0=0

for i=1,m  //Processing
  p = (dp +P[i]) mod q
  t_0 = (dt + T[i]) mod q
end for

for s=0,n-m //Matching
  if p=t_s
    if P[i..m]=T[s+1....s+m]
      print "Find it!"
    end if
  end if
  if s<n-m
    t_(s+1) =(  d(t_s - T[s+1]h ) + T[s+m+1]  ) mod q
  end if
end for