Karp Rabin algorithm

Karp Rabin algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text.It mainly useful for detecting plagiarism. Write a program to implement Karp Rabin algorithm

Algorithm Explanation

	Initialize with text and word, pass to the utility function.
	Iterate all the characters from the text and match with a pattern using KarpRabin string searching algorithm.
	Return the position of the string.

Source Code

package com.dsacode.DataStructre.array;
 
import java.util.Random;
import java.math.BigInteger;
 
public class StrMatchRabinKarp {
 
    private String pat;
    private long patHash;   
    private int M; 
    private long Q;
    private int R;  
    private long RM;         
 
    public StrMatchRabinKarp(String txt, String pat)  {
        this.pat = pat;     
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M-1; i++)
           RM = (R * RM) % Q;
        patHash = hash(pat, M);
       
    }
 
    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;
    }
     
     
    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;
    }
     
     
    private int search(String txt) {
        int N = txt.length();
        if (N < M) return N;
        long txtHash = hash(txt, M);
 
        if ((patHash == txtHash) && check(txt, 0))
            return 0;
 
        for (int i = M; i < N; i++)     {
 
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }
        return -1;
    }
     
     
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }
     
     
    public static void main(String[] args) {   
        System.out.println("String pattern match using Rabin Karp Algorithm");
 
        String t = "hfgbcabdabcabd", p = "ab";
        StrMatchRabinKarp bm = new StrMatchRabinKarp(t, p);
 
        System.out.println("String Text:" + t + " Pattern:" + p);
 
          int pos = bm.search(t);
            if (pos == -1)
                System.out.println("\nNo Match\n");
            else
                System.out.println("Pattern found at position : "+ pos);
    }
 
}

Output

String pattern match using Rabin Karp Algorithm
String Text:hfgbcabdabcabd Pattern:ab
Pattern found at position: 5