forked from matthewsamuel95/ACM-ICPC-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 1
/
rabin_karp_matcher.py
52 lines (48 loc) · 1.23 KB
/
rabin_karp_matcher.py
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
"""RABIN-KARP-MATCHER(T, P, d, q)
n = T.length
m = P.length
h = d^(m-1) mod q
p = 0
q = 0
t = 0
for i=1 to m
p = (d*p + P[i]) mod q
t = (d*t + T[i]) mod q
for s=0 to n-m
if p==t
if P[1..m] == T[s+1..s+m]
print"Pattern occurs with shift" s
if s < n-m
t^(s+1) = (d(t - T[s+1]h) + T[s+m+1]) mod q"""
def rabin_karp_matcher(T, P, d, q):
"""Rabin Karp algorithm for string matching
:T : input text
:P : pattern to find
:d : number of characters in the input text
:q : prime number"""
n = len(T)
m = len(P)
h = 1
p = 0
t = 0
# preprocessing
for i in range(m - 1):
h = (h * d) % q
for i in range(m):
p = (d * p + ord(P[i])) % q
t = (d * t + ord(T[i])) % q
# string matching
for s in range(n - m + 1):
if p == t:
for j in range(m):
if T[s + j] != P[j]:
break
j += 1
if j == m:
print("Pattern found at index: " + str(s))
if s < n - m:
t = (d * (t - ord(T[s]) * h) + ord(T[s + m])) % q
if t < 0: # for negative t
t += q
text = "JUSTANANOTHERTEXT"
rabin_karp_matcher(text, "AN", len(text), 13)