Breaking
Array

# 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

## 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```