Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8d00ff7

Browse files
author
shengshijun
committed
字符串朴素匹配算法:bugfix
Rabin-krap算法实现
1 parent85fce78 commit8d00ff7

File tree

2 files changed

+51
-2
lines changed

2 files changed

+51
-2
lines changed

‎string/rabin-karp.py

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
"""
5+
首先计算pattern字符串的hash值，然后在从目标字符串的开头，计算相同长度字符串的hash值。若hash值相同，则表示匹配，若不同，则向右移动一位，计算新的hash值。整个过程，与暴力的字符串匹配算法很相似，
6+
但由于计算hash值时，可以利用上一次的hash值，从而使新的hash值只需要加上新字母的计算，并减去上一次的第一个字母的计算，即可。
7+
Rabin-Karp算法的预处理时间为O(m)，最坏情况下该算法的匹配时间为O((n-m+1)m)，期望复杂度O(m+n)
8+
"""
9+
10+
11+
defmatch(origin,pattern):
12+
pattern_len=len(pattern)
13+
14+
def_hash(string,start=0):
15+
hash_code=0
16+
forxinxrange(pattern_len):
17+
hash_code+=ord(string[start+x])*2** (pattern_len-x-1)
18+
returnhash_code
19+
20+
def_refresh(old_hash,old_char,new_char):
21+
return (old_hash-ord(old_char)*2** (pattern_len-1))*2+ord(new_char)
22+
23+
deftest_equal(start_index):
24+
forxinxrange(pattern_len):
25+
iforigin[x+start_index]!=pattern[x]:
26+
returnFalse
27+
returnTrue
28+
29+
origin_index=0
30+
pattern_hash=_hash(pattern)
31+
origin_hash=_hash(origin)
32+
whileorigin_index<len(origin)-pattern_len-1:
33+
ifpattern_hash==origin_hashandtest_equal(origin_index):
34+
returnorigin_index
35+
else:
36+
print"origin hash:%s,pattern hash:%s"% (origin_hash,pattern_hash)
37+
origin_hash=_refresh(origin_hash,origin[origin_index],origin[origin_index+pattern_len])
38+
origin_index+=1
39+
40+
41+
defmain():
42+
printmatch("sbsfsdgdgfgasbssssfsfdfeferf",'sb')
43+
44+
45+
if__name__=="__main__":
46+
main()

‎string/simple.py

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,22 +5,25 @@
55

66
defmatch(origin,pattern):
77
origin_index,pattern_index=0,0
8+
match_flag=True
89
pattern_len=len(pattern)
910
whileorigin_index<len(origin):
1011
forpattern_indexinxrange(pattern_len):
1112
ifpattern[pattern_index]!=origin[origin_index]:
1213
origin_index-= (pattern_index-1)
14+
match_flag=False
1315
break
1416
else:
1517
origin_index+=1
1618
pattern_index+=1
19+
match_flag=True
1720

18-
iforigin[origin_index]==pattern[pattern_index]:
21+
ifmatch_flag:
1922
returnorigin_index-pattern_index
2023

2124

2225
defmain():
23-
printmatch("absbsbshdhhd",'sb')
26+
printmatch("absabsvbshsbdhhd",'sb')
2427

2528

2629
if__name__=="__main__":

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp