Rabin Karp Algorithm

There are couple string match algorithms which can achieve linear time to do the search in stead of O(n*m). Suffix tree algorithm requires to pre-compute the suffix tree and requires O(K*N) space, K is the alphabet size and N is the maximum length of the strings. KPM also needs to pre-compute a table of  failure function to quickly find the next starting positions in two string. Rabin Karp algorithm is probably the simplest one, which use hash to compare two strings.

The key to Rabin Karp algorithm is to compute the hash effectively and quickly. This is done by dynamic programming, which is current substring hash value is computed based on the previous one. 

Here is the Rabin Karp algorithm to solve an online algorithm for palindrome checking.

	package org.blueocean;
	public class RabinKarpString {
	static final int prime = 101;
	static final int base = 103;
	public static void rabinKarp(String s){
	assert(s!=null && !s.isEmpty());
	long leftHash = s.charAt(0);
	long rightHash = s.charAt(0);
	System.out.println("Yes");
	int h = 1;
	for(int i = 1; i < s.length(); i++){
	h = (h*prime)%base;
	leftHash = (leftHash*prime + s.charAt(i))%base;
	rightHash = ( (long) (s.charAt(i)*h + rightHash))%base;
	if(leftHash == rightHash){
	isPali(s, i);
	}else
	System.out.println("No");
	}
	}
	public static void isPali(String s, int i){
	for(int l=0,r=i; l<=r; l++, r--){
	if(s.charAt(l) != s.charAt(r)){
	System.out.println("No");
	}
	}
	System.out.println("Yes");
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

Thanks to Peng Li for bringing up this problem. Here is the link to his page on this: http://allenlipeng47.com/PersonalPage/index/view/157/nkey