Implement the Rabin–Karp matcher string matching algorithm.

Here,first I explains that what is String matching? and then i will write a java program to implement the Rabin – Karp matcher string matching algorithm.

What is String matching?

String matching is the technique of finding the instance of a character pattern in a given string.

• Rabin-Karp algorithm is used for finding the numeric pattern in a given text.

now,lets see java program to implement the Rabin – Karp matcher string 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; 
    private long patHash;    
    private int M;  
    private long Q; 
    private int R;   
    private long RM;          
 
    public RabinKarp(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);
        int pos = search(txt);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : "+ pos);
    } 
    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) 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);        
    }
}

OUTPUT: