forked from ssjssh/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathkmp.py
More file actions
44 lines (32 loc) · 1.25 KB
/
kmp.py
File metadata and controls
44 lines (32 loc) · 1.25 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
#!/usr/bin/env python
# -*- coding:UTF-8
__author__ = 'shenshijun'
def match(origin, pattern):
origin_len = len(origin)
pattern_len = len(pattern)
def build_next():
_next_list = [0 for x in xrange(pattern_len)]
last_match = 0
for cur_index in xrange(1, pattern_len):
while last_match > 0 and pattern[last_match] != pattern[cur_index]:
last_match = _next_list[last_match]
if pattern[last_match] == pattern[cur_index]:
last_match += 1
_next_list[cur_index] = last_match
return _next_list
origin_index, pattern_index = 0, 0
next_list = build_next()
print(next_list)
while origin_index < origin_len:
# while需要放在前面，如果放在后面的话且有匹配的情况下pattern[pattern_index]就会越界
while pattern_index > 0 and origin[origin_index] != pattern[pattern_index]:
pattern_index = next_list[pattern_index]
if pattern[pattern_index] == origin[origin_index]:
pattern_index += 1
origin_index += 1
if pattern_index == pattern_len:
return origin_index - pattern_len
def main():
print match("assssbsss", 'sb')
if __name__ == "__main__":
main()