forked from prabhupant/python-ds
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKMP_Pattern_Search.py
More file actions
57 lines (46 loc) · 1.41 KB
/
KMP_Pattern_Search.py
File metadata and controls
57 lines (46 loc) · 1.41 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
#Python program for KMP Algorithm
def KMP_pattern_search(pattern, text):
P = len(pattern)
Q = len(text)
# create long_prefix_suffix[] that will hold the longest prefix suffix
# values for pattern
long_prefix_suffix = [0]*P
# index for pattern[]
j=0
# preprocess the pattern (caluclate long_prefix_suffix[] array)
long_Prefix_Suffix_Array(pattern, P, long_prefix_suffix)
# index for text[]
i=0
while i < Q:
if pattern[j] == text[i]:
i += 1
j += 1
if j == P:
print("Pattern found at index " + str(i-j))
j=long_prefix_suffix[j-1]
# mismatch after j matches
elif i < Q and pattern[j] != text[i]:
if j != 0:
j=long_prefix_suffix[j-1]
else:
i += 1
def long_Prefix_Suffix_Array(pattern, P, long_prefix_suffix):
# length of the previous longest prefix suffix
l=0
long_prefix_suffix[0]=0
i=1
# the loop calculates long_prefix_suffix[i] for i = 1 to P-1
while i < P:
if pattern[i] == pattern[l]:
l += 1
long_prefix_suffix[i] = l
i += 1
else:
if l != 0:
l=long_prefix_suffix[l-1]
else:
long_prefix_suffix[i] = 0
i += 1
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
KMP_pattern_search(pattern, text)