Java Program to Implement Rabin-Karp Method for Pattern Searching

«
»
This is a Java Program to Implement Rabin Karp Pattern Matching Algorithm. The Rabin–Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text.

Here is the source code of the Java Program to Implement Rabin Karp Pattern Matching Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Rabin Karp Pattern Matching Algorithm
  3.  **/
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7. import java.io.IOException;
  8. import java.util.Random;
  9. import java.math.BigInteger;
  10.  
  11. public class RabinKarp 
  12. {
  13.     /** String Pattern **/
  14.     private String pat; 
  15.     /** pattern hash value **/    
  16.     private long patHash;    
  17.     /** pattern length **/
  18.     private int M;  
  19.     /** Large prime **/         
  20.     private long Q; 
  21.     /** radix **/         
  22.     private int R;   
  23.     /** R^(M-1) % Q **/        
  24.     private long RM;          
  25.  
  26.     /** Constructor **/
  27.     public RabinKarp(String txt, String pat) 
  28.     {
  29.         this.pat = pat;      
  30.         R = 256;
  31.         M = pat.length();
  32.         Q = longRandomPrime();
  33.         /** precompute R^(M-1) % Q for use in removing leading digit **/
  34.         RM = 1;
  35.         for (int i = 1; i <= M-1; i++)
  36.            RM = (R * RM) % Q;
  37.         patHash = hash(pat, M);
  38.         int pos = search(txt);
  39.         if (pos == -1)
  40.             System.out.println("\nNo Match\n");
  41.         else
  42.             System.out.println("Pattern found at position : "+ pos);
  43.     } 
  44.     /** Compute hash **/
  45.     private long hash(String key, int M)
  46.     { 
  47.         long h = 0; 
  48.         for (int j = 0; j < M; j++) 
  49.             h = (R * h + key.charAt(j)) % Q; 
  50.         return h; 
  51.     } 
  52.     /** Funtion check **/
  53.     private boolean check(String txt, int i) 
  54.     {
  55.         for (int j = 0; j < M; j++) 
  56.             if (pat.charAt(j) != txt.charAt(i + j)) 
  57.                 return false; 
  58.         return true;
  59.     }
  60.     /** Funtion to check for exact match**/
  61.     private int search(String txt) 
  62.     {
  63.         int N = txt.length(); 
  64.         if (N < M) return N;
  65.         long txtHash = hash(txt, M); 
  66.         /** check for match at start **/
  67.         if ((patHash == txtHash) && check(txt, 0))
  68.             return 0;
  69.         /** check for hash match. if hash match then check for exact match**/
  70.         for (int i = M; i < N; i++) 
  71.         {
  72.             // Remove leading digit, add trailing digit, check for match. 
  73.             txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q; 
  74.             txtHash = (txtHash * R + txt.charAt(i)) % Q; 
  75.             // match
  76.             int offset = i - M + 1;
  77.             if ((patHash == txtHash) && check(txt, offset))
  78.                 return offset;
  79.         }
  80.         /** no match **/
  81.         return -1;
  82.     }
  83.     /** generate a random 31 bit prime **/
  84.     private static long longRandomPrime() 
  85.     {
  86.         BigInteger prime = BigInteger.probablePrime(31, new Random());
  87.         return prime.longValue();
  88.     }
  89.     /** Main Function **/
  90.     public static void main(String[] args) throws IOException
  91.     {    
  92.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  93.         System.out.println("Rabin Karp Algorithm Test\n");
  94.         System.out.println("\nEnter Text\n");
  95.         String text = br.readLine();
  96.         System.out.println("\nEnter Pattern\n");
  97.         String pattern = br.readLine();
  98.         System.out.println("\nResults : \n");
  99.         RabinKarp rk = new RabinKarp(text, pattern);        
  100.     }
  101. }

Rabin Karp Algorithm Test
 
 
Enter Text
 
abcdefghijklmnopqrstuvwxyz
 
Enter Pattern
 
jklmn
 
Results :
 
Pattern found at position : 9

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.