FilesExpand file tree

 master

/

knuthmorrispratt.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (42 loc) · 1.08 KB

 master

/

knuthmorrispratt.py

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (42 loc) · 1.08 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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)