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