[Algorithm][String Pattern Match]

Rabin–Karp

function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]);  hs := hash(s[1..m]) // Compute input string's hash with length of pattern's string
for i from 1 to n-m+1
  if hs = hsub
    if s[i..i+m-1] = sub   //Since might hash collision, double check if the sub-string is really a match
      return i
  hs := hash(s[i+1..i+m])  // Use rolling hash here. O(mn) for worst case.
return not found

rolling hash
C++ Implement of rolling hash
C++ Implement of rolling hash