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:
Guide to java.util.concurrent.BlockingQueue
Biến trong java
Spring Boot - Tracing Micro Service Logs
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java 8 StringJoiner
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement Sorted List
Introduction to Spring Security Expressions
Java String to InputStream
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Comparing Long Values in Java
Guide to the Java ArrayList
String Initialization in Java
Debugging Reactive Streams in Java
Pagination and Sorting using Spring Data JPA
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
A Comparison Between Spring and Spring Boot
A Guide to Spring Cloud Netflix – Hystrix
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Find Maximum Element in an Array using Binary Search
Java Program to Perform the Shaker Sort
Một số từ khóa trong Java
Java – Rename or Move a File
Control the Session with Spring Security
Spring Boot - Rest Template
Introduction to Using Thymeleaf in Spring
Java – Create a File
Sort a HashMap in Java
Java Program to Implement Gauss Seidel Method
Serialize Only Fields that meet a Custom Criteria with Jackson
Updating your Password
Semaphore trong Java