Rabin Karp pattern Matching Algorithm

/**
 ** Java Program to Implement Rabin Karp Pattern Matching Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;
import java.math.BigInteger;

public class RabinKarp
{
    private String pat; /** String Pattern **/
    private long patHash; /** pattern hash value **/
    private int M;   /** pattern length **/
    private long Q; /** Large prime **/
    private int R; /** radix **/
    private long RM; /** R^(M-1) % Q **/
    private int KeyCount; /** key operation counter **/

    public RabinKarp(String txt, String pat) /** Constructor **/
    {
        this.pat = pat;
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        KeyCount = 0;

        /** 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 == -1)
            System.out.println("\nNo Match\n");
        else {
        System.out.println("Pattern found at position : "+ pos);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** 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++){
        KeyCount++;
        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);

        if ((patHash == txtHash) && check(txt, 0)) /** check for match at start **/
            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;
        }

        return -1; /** no match **/
    }

    /** generate a random 31 bit prime **/
    private static long longRandomPrime()
    {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    /** Main Function **/
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Rabin Karp Algorithm 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);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input/Output:

Rabin Karp Algorithm Test

Enter Text

Hello How are you

Enter Pattern

are

Results : 

Pattern found at position : 10

No of comparisons : 3

(Please note: WTF   #$@%!^^ Just 3)