forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathknuthmorrispratt.py
More file actions
49 lines (42 loc) · 1.08 KB
/
knuthmorrispratt.py
File metadata and controls
49 lines (42 loc) · 1.08 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
# Knuth-Morris-Pratt algorithm
# Compute temporary array to maintain size of suffix which is same as prefix
# Time/space complexity is O(size of pattern)
def compute_temporary_array(pattern):
n = len(pattern)
lsp = [0 for j in range(n)]
index = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[index]:
lsp[i] = index + 1
index += 1
i += 1
else:
if index != 0:
index = lsp[index - 1]
else:
lsp[i] = 0
i += 1
return lsp
# KMP algorithm of pattern matching.
def kmp(text, pattern):
lsp = compute_temporary_array(pattern)
i = 0
j = 0
while i < len(text) and j < len(pattern):
if text[i] == pattern[j]:
i += 1
j += 1
else:
if j != 0:
j = lsp[j - 1]
else:
i += 1
if j == len(pattern):
return True
else:
return False
src = 'abcxabcdabcdabcy'
sub_string = 'abcdabcy'
result = kmp(src, sub_string)
print(result)