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 Implement Hash Tables
Java Program to Generate Random Numbers Using Probability Distribution Function
String Initialization in Java
Check if there is mail waiting
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Extract network card address
An Intro to Spring Cloud Task
Java Program to implement Array Deque
Biến trong java
Java Program to Implement RenderingHints API
SOAP Web service: Authentication trong JAX-WS
Lớp TreeMap trong Java
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Serve Static Resources with Spring
Một số từ khóa trong Java
Filtering a Stream of Optionals in Java
Guide to WeakHashMap in Java
Spring MVC + Thymeleaf 3.0: New Features
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Java Program to Implement Bellman-Ford Algorithm
Java Program to Find Strongly Connected Components in Graphs
Jackson – Unmarshall to Collection/Array
Circular Dependencies in Spring
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
OAuth2.0 and Dynamic Client Registration
A Custom Media Type for a Spring REST API
Practical Java Examples of the Big O Notation
Java Program to Find Transpose of a Graph Matrix
Derived Query Methods in Spring Data JPA Repositories
Fixing 401s with CORS Preflights and Spring Security
Iterating over Enum Values in Java
Java Program to Print only Odd Numbered Levels of a Tree