Repository navigation
Expand file tree
/
Copy pathRabinKarp.java
More file actions
79 lines (63 loc) · 2.51 KB
/
Copy pathRabinKarp.java
File metadata and controls
79 lines (63 loc) · 2.51 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/** @author Prateek Kumar Oraon (https://github.com/prateekKrOraon) */
import java.util.Scanner;
// An implementation of Rabin-Karp string matching algorithm
// Program will simply end if there is no match
public class RabinKarp {
public static Scanner scanner = null;
public static final int d = 256;
public static void main(String[] args) {
scanner = new Scanner(System.in);
System.out.println("Enter String");
String text = scanner.nextLine();
System.out.println("Enter pattern");
String pattern = scanner.nextLine();
int q = 101;
searchPat(text, pattern, q);
}
private static void searchPat(String text, String pattern, int q) {
int m = pattern.length();
int n = text.length();
int t = 0;
int p = 0;
int h = 1;
int j = 0;
int i = 0;
h = (int) Math.pow(d, m - 1) % q;
for (i = 0; i < m; i++) {
// hash value is calculated for each character and then added with the hash value of the next
// character for pattern
// as well as the text for length equal to the length of pattern
p = (d * p + pattern.charAt(i)) % q;
t = (d * t + text.charAt(i)) % q;
}
for (i = 0; i <= n - m; i++) {
// if the calculated hash value of the pattern and text matches then
// all the characters of the pattern is matched with the text of length equal to length of the
// pattern
// if all matches then pattern exist in string
// if not then the hash value of the first character of the text is subtracted and hash value
// of the next character after the end
// of the evaluated characters is added
if (p == t) {
// if hash value matches then the individual characters are matched
for (j = 0; j < m; j++) {
// if not matched then break out of the loop
if (text.charAt(i + j) != pattern.charAt(j)) break;
}
// if all characters are matched then pattern exist in the string
if (j == m) {
System.out.println("Pattern found at index " + i);
}
}
// if i<n-m then hash value of the first character of the text is subtracted and hash value of
// the next character after the end
// of the evaluated characters is added to get the hash value of the next window of characters
// in the text
if (i < n - m) {
t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;
// if hash value becomes less than zero than q is added to make it positive
if (t < 0) t = (t + q);
}
}
}
}