-
Notifications
You must be signed in to change notification settings - Fork 0
/
KMP2.py
78 lines (67 loc) · 1.95 KB
/
KMP2.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
"""
KMP算法:字串搜尋
"""
# TEST 2 (Target尾部加長,有兩個符合條件的位置)
"""
Target = abaabcababcabacababc
Pattern = ababc
"""
Target = "abaabcababcabacababc"
Pattern = "ababc"
"""
自動建立前綴表
"""
prefixTable = dict()
for i in range(len(Pattern)):
prefixTable[Pattern[:i+1]] = None
"""
自動填寫前綴表數值,數值為該鍵最大前後綴相等長度
"""
for key in prefixTable:
maxLen = 0
for i in range(len(key)//2):
if key[:i+1] == key[-i-1:]:
maxLen = max(maxLen, i+1)
prefixTable[key] = maxLen
"""
移動前綴表數值
"""
prev = -1
for key in prefixTable:
prefixTable[key], prev = prev, prefixTable[key]
#
print(prefixTable)
# 實踐 KMP 搜尋
Target
Pattern
prefixTable
result = []
prefixTable_index = 0
Target_index = 0
len_Target = len(Target)
len_Pattern = len(Pattern)
while Target_index < len_Target - len_Pattern + 1:
# 開始匹配,直到 prefixTable_index 來到 -1 或是 全匹配為止。
while prefixTable_index > -1 and prefixTable_index < len_Pattern:
if Pattern[prefixTable_index] == Target[Target_index]:
Target_index += 1
prefixTable_index += 1
else:
prefixTableKey = Pattern[:prefixTable_index+1]
prefixTable_index = prefixTable[prefixTableKey]
# 不是 prefixTable_index == -1 就是 prefixTable_index == len_Pattern(全匹配)
if prefixTable_index == -1:
prefixTable_index = 0 #從P[0]開始
else:
# 如果全匹配就繼續搜尋
result.append(Target_index-len_Pattern)
prefixTable_index = prefixTable[Pattern]
Target_index += 1 #往下一位搜尋
"""
Target = "abcabc「a」babcabac「a」babc"
Pattern = "ababc"
"""
if result:
print("搜尋結果:{:} ".format(result))
else:
print("搜尋結果:{:} 無匹配位置".format(result))