Java Program to Implement Rolling Hash

«
»
This is a Java Program to implement Rolling Hash. Here Rabin Karp algorithm is implemented using Rolling Hash.

Here is the source code of the Java program to implement Rolling Hash. 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 Rolling Hash
  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. 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 == txt.length())
  40.             System.out.println("\nNo Match\n");
  41.         else
  42.             System.out.println("Pattern found at : "+ 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 N;
  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. }
  90.  
  91. /** Class RollingHashTest **/
  92. public class RollingHashTest
  93. {
  94.     public static void main(String[] args) throws IOException
  95.     {    
  96.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  97.         System.out.println("Rolling Hash Test\n");
  98.         System.out.println("\nEnter Text\n");
  99.         String text = br.readLine();
  100.         System.out.println("\nEnter Pattern\n");
  101.         String pattern = br.readLine();
  102.         System.out.println("\nResults : \n");
  103.         RabinKarp rk = new RabinKarp(text, pattern);        
  104.     }
  105. }

advertisement
Rolling Hash Test
 
 
Enter Text
 
abcdefghijklmnopqrstuvwxyz
 
Enter Pattern
 
jklmn
 
Results :
 
Pattern found at : 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.