forked from rishabhgarg25699/Competitive-Programming
-
Notifications
You must be signed in to change notification settings - Fork 0
/
KMP.py
45 lines (41 loc) · 926 Bytes
/
KMP.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
def get_ind(pattern):
b = len(pattern)
ind = []
for i in range(0,b):
ind.append(0)
n=0
m=1
while m!= b:
if pattern[m] == pattern[n]:
n += 1
ind[m] = n
m += 1
elif n!= 0:
n = prefix_arr[n-1]
else:
ind[m] = 0
m += 1
return ind
def KMP(pattern, text):
a = len(text)
b = len(pattern)
ind = get_ind(pattern)
initial = []
m=0
n=0
while m!= a:
if text[m] == pattern[n]:
n += 1
m += 1
else:
n = ind[n-1]
if n == b:
initial.append(m-n)
n = ind[n-1]
elif n == 0:
m += 1
return initial
pattern = str(input("Enter the patter nto be found: "))
text = str(input("Enter the complete text: "))
initial = KMP(pattern, text)
print("The starting index are: ", initial)