[Algorithm] Rabin-Karp Algorithm

Given a String S and a String P, assume the length of S is larger than P, find the first occurrence of P in S.

This is a very classical problem, a very naive method is just to from S[0] to S[n-m], we check each substring if it is the same with P, the time complexity is O(mn). Another method is called KMP algorithm and it has better time complexity O(n+m), but the coding complexity is quite high. Rabin-Karp is a quite easy algorithm and its average running time is O(m+n).

The core idea is HASH. It also sweep from S[0] to S[n-m], however, it improves the process of checking if the substring S[i...i+m] is the same with P by per-compute a hash for P and the substring. If the hash is not the same, then we are sure that the two string could not be the same, if they are the same, then we check if the two string is the same. The hash code of S[i...i+m-1]is compute as

hash = (S[m-1+i]*d^0 + S[m-2+i]*d^1 + ... + S[i]*d^(m-1)) mod q, here q is prime

Then, we could quick recompute the hash code of S[i+1...i+m] as

new_hash = ((hash - S[i]*d^(m-1)) * d + S[i+m]) mod q

This technique is called rolling hash. In this way we could re-compute the new hash based on the old one in O(1) time.

Below is my implement of the Rabin-Karp, if there is mistake, please contact me

import java.util.*;
 public class Rabin_karp {
 public static int search(String S, String P) {
  int n = S.length();
  int m = P.length();
  if(n < m)
   return -1;

  int h1 = 0; // hash number of String S
  int h2 = 0; // hash number of String P
  int d = 256;
  int h = 1;
  int q = 9973;

  // the value of h would be "pow(d, M-1) % q"
  for(int i = 0; i < m-1; i++) {
   h = (h * d) % q;
  }

  for(int i = 0; i < m; i++) {
   h1 = (h1 * d + S.charAt(i)) % q;
   h2 = (h2 * d + P.charAt(i)) % q;
  }
  System.out.println(h2);
  for(int i = 0; i <= n-m; i++) {
   System.out.println(S.substring(i, i+m) + " " + h1);
   if(h1 == h2) {
    boolean find = true;
    for(int j = 0; j < m; j++) {
     if(S.charAt(i+j) != P.charAt(j)) {
      find = false;
      break;
     }
    }
    if(find == true)
     return i;
   }
   else {
    if(i < n - m)
     h1 = (d * (h1 - h * S.charAt(i)) + S.charAt(i + m)) % q;
    if(h1 < 0)
     h1 = h1 + q;
   }
  }

  return -1;
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   String s = scan.next();
   String p = scan.next();
   System.out.println(search(s, p));
  }
 }
}

Reference: http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/