Simple Java program for Rabin-Karp Algorithm

class rabinKarp{

public static void main(String[] args){

String txt="abcdefghijhsfdjghdsfjhgjkfdsfghk"; //test data

String ptn="fgh";

int n=txt.length();//get the lenght of the given text

int m=ptn.length();//get the lenght of the pattern given

int hashOfPatt= ptn.hashCode(); //get the hash value of the pattern

/*a loop runs shorter than the text lenght to find out the hashes tally each other*/

for(int i=0;i<n;i++){

if(i+m+1<=n){

String sub=txt.substring(i,i+m);//split the text consecutively by lenght of the pattern

int hashOfSub=sub.hashCode(); //check hash of the text and hash of the pattern match each other

if(hashOfPatt==hashOfSub){ //if the pattern and text tallies, then start character by character checking

int k=0;

boolean d=true;

/*loop runs through both the selected parts to check whether both the parts match each other*/

for(int j=i;j<i+m;j++){ 

if(txt.charAt(j)==ptn.charAt(k)){ 

k++;

}

else{

d=false;

break; //end ot loop when a un matchable part found

}

}

if(d){

System.out.println(sub); //print the pattern each and every time a match found

}

}

}

}

}

}

Tweet

Pin It