forked from sphinxyun/algorithm-in-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrabin_karp.py
More file actions
60 lines (56 loc) · 1.42 KB
/
rabin_karp.py
File metadata and controls
60 lines (56 loc) · 1.42 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
#coding: utf-8
''' mbinary
#########################################################################
# File : rabin_karp.py
# Author: mbinary
# Mail: [email protected]
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-12-11 00:01
# Description: rabin-karp algorithm
#########################################################################
'''
def isPrime(x):
for i in range(2,int(x**0.5)+1):
if x%i==0:return False
return True
def getPrime(x):
'''return a prime which is bigger than x'''
for i in range(x,2*x):
if isPrime(i):return i
def findAll(s,p):
'''s: string p: pattern'''
dic={}
n,m = len(s),len(p)
d=0 #radix
for c in s:
if c not in dic:
dic[c]=d
d+=1
sm = 0
for c in p:
if c not in dic:return []
sm = sm*d+dic[c]
ret = []
cur = 0
for i in range(m): cur=cur*d + dic[s[i]]
if cur==sm:ret.append(0)
tmp = n-m
q = getPrime(m)
cur = cur%q
sm = sm%q
exp = d**(m-1) % q
for i in range(m,n):
cur = ((cur-dic[s[i-m]]*exp)*d+dic[s[i]]) % q
if cur == sm and p==s[i-m+1:i+1]:
ret.append(i-m+1)
return ret
def randStr(n=3):
return [randint(ord('a'),ord('z')) for i in range(n)]
if __name__ =='__main__':
from random import randint
s = randStr(50)
p = randStr(1)
print(s)
print(p)
print(findAll(s,p))