Java Program to Implement Rolling Hash

2021 VietMX JAVA 0

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
 * 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);       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Rolling Hash Test
  
  
Enter Text
  
abcdefghijklmnopqrstuvwxyz
  
Enter Pattern
  
jklmn
  
Results :
  
Pattern found at : 9

Related posts:

Spring Data – CrudRepository save() Method
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
How to Get All Dates Between Two Dates?
Java Program to Implement IdentityHashMap API
Java Program to Implement Nth Root Algorithm
Spring Security Logout
Java Scanner hasNext() vs. hasNextLine()
Java Program to Evaluate an Expression using Stacks
Spring Cloud Bus
Java Program to Find Path Between Two Nodes in a Graph
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
The Basics of Java Security
Tạo số và chuỗi ngẫu nhiên trong Java
Java Program to Perform Addition Operation Using Bitwise Operators
Spring Boot - Tomcat Deployment
Jackson vs Gson
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Sending Emails with Java
Java Program to Encode a Message Using Playfair Cipher
Arrays.asList vs new ArrayList(Arrays.asList())
Creating Docker Images with Spring Boot
Count Occurrences of a Char in a String
Receive email by java client
Quick Guide to Spring Bean Scopes
Java Program to Implement Hash Tables Chaining with List Heads
Introduction to Thread Pools in Java
Anonymous Classes in Java
Servlet 3 Async Support with Spring MVC and Spring Security
Phân biệt JVM, JRE, JDK
Java Program to Implement Ford–Fulkerson Algorithm
Java Program to Implement Self organizing List