-
Notifications
You must be signed in to change notification settings - Fork 0
/
TugasSM-KMP.py
56 lines (54 loc) · 1.24 KB
/
TugasSM-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
46
47
48
49
50
51
52
53
54
55
56
def cfail(pola):
fail = [None] * len(pola)
fail[0]=0
m = len(pola)
j = 0
i = 1
#while . . .
while (i < m):
if (pola[j] == pola[i]) :
#j+1 chars match
fail[i] = j + 1
i= i+1
j= j+1
elif (j > 0):
# j follows matching prefix
j = fail[j-1];
else: # no match
fail[i] = 0
i= i+1
return fail
def searchKMP(T,P):
fail = cfail(P)
n = len(T)
m = len(P)
i = 0
j = 0
Found = False
#while ……
while (i < n) and (not Found):
if (P[j] == T[i]):
if (j == m-1):
Found = True
hasil = i-m+1
else:
j = j + 1
i = i + 1
elif (j > 0):
print("i=",i)
print(f'j= F({j-1})= ',end="")
j = fail[j-1]
print(f'{j}')
else:
i = i + 1
print("i=",i)
print(f'j= {j}')
if (not Found):
hasil = -1
return hasil
def main():
T = str(input("Teks:"))
P = str(input("Pola:"))
print(searchKMP(T,P))
if __name__ == '__main__':
main()