-
Notifications
You must be signed in to change notification settings - Fork 38
/
Rabin Karp Algorithm for Pattern Searching
63 lines (54 loc) · 1.85 KB
/
Rabin Karp Algorithm for Pattern Searching
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
/*
Rabin-Karp Algorithm for Pattern Searching
Rabin-Karp algorithm is an algorithm used for searching/matching patterns in the text using
a hash function. Unlike Naive string matching algorithm, it does not travel through every
character in the initial phase rather it filters the characters that do not match and then
performs the comparison.
For example
Input: txt[] = “AABAACAADAABAABA”, pat[] = “AABA”
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
*/
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
// Slide the pattern over text one by one
for (i = 0; i <= N - M; i++) {
// Check the hash values of current window of text
// and pattern. If the hash values match then only
// check for characters one by one
if (p == t) {
/* Check for characters one by one */
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
// if p == t and pat[0...M-1] = txt[i, i+1,
// ...i+M-1]
if (j == M)
cout<< "Pattern found at index " << i<< endl;
}
// Calculate hash value for next window of text:
// Remove leading digit, add trailing digit
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
// We might get negative value of t, converting
// it to positive
if (t < 0)
t = (t + q);
}
}
}