/
kmpPatternMatching.py
42 lines (37 loc) · 1.03 KB
/
kmpPatternMatching.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
def computeLps(patternArr, patternArrLength):
lps = [0] * patternArrLength
i = 1
j = 0
while i < patternArrLength:
if patternArr[i] == patternArr[j]:
lps[i] = j + 1
i += 1
j += 1
else:
if j == 0:
lps[i] = 0
i += 1
else:
j = lps[j-1]
return lps
def kmp(mainArr, patternArr):
mainArrLength = len(mainArr)
patternArrLength = len(patternArr)
lps = computeLps(patternArr, patternArrLength)
i = 0
j = 0
while i < mainArrLength and j < patternArrLength:
if mainArr[i] == patternArr[j]:
i += 1
j += 1
else:
if j == 0:
i += 1
else:
j = lps[j-1]
if j == patternArrLength:
return "Pattern found starting at index " + str(i - patternArrLength) + " in the main String"
return "Pattern not found"
mainStr = "abcxabcdabcdabcy"
pattern = "dabcy"
print kmp(list(mainStr), list(pattern))