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.
/** * Java Program to Implement Rolling Hash **/ import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Random; import java.math.BigInteger; class RabinKarp { /** String Pattern **/ private String pat; /** pattern hash value **/ private long patHash; /** pattern length **/ private int M; /** Large prime **/ private long Q; /** radix **/ private int R; /** R^(M-1) % Q **/ private long RM; /** Constructor **/ public RabinKarp(String txt, String pat) { this.pat = pat; R = 256; M = pat.length(); Q = longRandomPrime(); /** precompute R^(M-1) % Q for use in removing leading digit **/ RM = 1; for (int i = 1; i <= M-1; i++) RM = (R * RM) % Q; patHash = hash(pat, M); int pos = search(txt); if (pos == txt.length()) System.out.println("\nNo Match\n"); else System.out.println("Pattern found at : "+ pos); } /** Compute hash **/ private long hash(String key, int M) { long h = 0; for (int j = 0; j < M; j++) h = (R * h + key.charAt(j)) % Q; return h; } /** Funtion check **/ private boolean check(String txt, int i) { for (int j = 0; j < M; j++) if (pat.charAt(j) != txt.charAt(i + j)) return false; return true; } /** Funtion to check for exact match**/ private int search(String txt) { int N = txt.length(); if (N < M) return N; long txtHash = hash(txt, M); /** check for match at start **/ if ((patHash == txtHash) && check(txt, 0)) return 0; /** check for hash match. if hash match then check for exact match**/ for (int i = M; i < N; i++) { // Remove leading digit, add trailing digit, check for match. txtHash = (txtHash + Q - RM*txt.charAt(i - M) % Q) % Q; txtHash = (txtHash * R + txt.charAt(i)) % Q; // match int offset = i - M + 1; if ((patHash == txtHash) && check(txt, offset)) return offset; } /** no match **/ return N; } /** generate a random 31 bit prime **/ private static long longRandomPrime() { BigInteger prime = BigInteger.probablePrime(31, new Random()); return prime.longValue(); } } /** Class RollingHashTest **/ public class RollingHashTest { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Rolling Hash Test\n"); System.out.println("\nEnter Text\n"); String text = br.readLine(); System.out.println("\nEnter Pattern\n"); String pattern = br.readLine(); System.out.println("\nResults : \n"); RabinKarp rk = new RabinKarp(text, pattern); } }
Rolling Hash Test Enter Text abcdefghijklmnopqrstuvwxyz Enter Pattern jklmn Results : Pattern found at : 9
Related posts:
Java Program to Generate a Random Subset by Coin Flipping
Check if a String is a Palindrome in Java
Command-Line Arguments in Java
Java TreeMap vs HashMap
HTTP Authentification and CGI/Servlet
Introduction to Netflix Archaius with Spring Cloud
Simple Single Sign-On with Spring Security OAuth2
Introduction to Spliterator in Java
Enum trong java
Java – Reader to Byte Array
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Implement Karatsuba Multiplication Algorithm
Java Program to Permute All Letters of an Input String
A Guide to the finalize Method in Java
RegEx for matching Date Pattern in Java
LinkedHashSet trong java
Java Program to implement Sparse Vector
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Using Spring ResponseEntity to Manipulate the HTTP Response
Spring Boot with Multiple SQL Import Files
Java 8 – Powerful Comparison with Lambdas
Java – Byte Array to Reader
Java Program to Implement Horner Algorithm
Java Program to Find Basis and Dimension of a Matrix
Java Program to Implement SimpeBindings API
Overview of the java.util.concurrent
Guava – Join and Split Collections
Java Program to Describe the Representation of Graph using Incidence Matrix
Predicate trong Java 8
Java Program to Implement Nth Root Algorithm
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Java Program to Implement Jarvis Algorithm