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:
Spring Boot - Sending Email
Java Program to Check if a Given Binary Tree is an AVL Tree or Not
Java Program to Implement Splay Tree
Spring Boot - Google OAuth2 Sign-In
Java Program to Implement Self Balancing Binary Search Tree
Java Program to Implement RenderingHints API
Java – Rename or Move a File
The Spring @Controller and @RestController Annotations
Spring Boot Actuator
Getting the Size of an Iterable in Java
An Example of Load Balancing with Zuul and Eureka
Guide to Java Instrumentation
Generating Random Dates in Java
Tìm hiểu về xác thực và phân quyền trong ứng dụng
How to Get the Last Element of a Stream in Java?
Java Program to Solve any Linear Equation in One Variable
Receive email using POP3
Hướng dẫn Java Design Pattern – Interpreter
Spring Boot with Multiple SQL Import Files
Spring Boot - CORS Support
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Java 8 Collectors toMap
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
Spring Data JPA and Null Parameters
Wrapper Classes in Java
Hướng dẫn Java Design Pattern – MVC
Guide to the Java Clock Class
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Java Switch Statement
MyBatis with Spring
Converting a List to String in Java
How to Delay Code Execution in Java