KMP Pattern Search Algorithm

Pattern Search Algorithm. Explains how both the Naive and KMP Pattern Search algorithm.

1. @ daywithalgorithm KMP Pattern Search Created By: Donald K nuth, James H. M orris, Vaughan P ratt.

2. @ daywithalgorithm 1. Why Should you Use this Algorithm for Pattern Search ? In order to know the reason, we shall revisit the process that is undertaken in the naive algorithm. By doing so, you will be understanding the reason behind it. The pattern (search text) is usually represented as needle and the paragraph or the text where we are searching is called as Haystack.

3. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH Text : 1 2 3 4 5 6 7 8 9 Index of Text : O N I O N S Pattern : 1 2 3 4 5 Index of Pattern :

4. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 0 ctr = 0

5. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 1 ctr = 1

6. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 2 ctr = 2

7. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 3 ctr = 3

8. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 4 ctr = 4

9. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 5 Not a Match

10. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 1 ctr = 0 Not a Match Here we’re re-inventing the wheel

11. @ daywithalgorithm O N I O N I O N S O NAIVE APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 3 ctr = 0 Time Complexity : Best Case Average Case Worst Case O(N) O(N-M) O(N*M)

12. @ daywithalgorithm Inorder to stop reinventing the wheel, we need to make a track of the values that we traversed. That could be acheived by Longest Prefix also Suffix Method.

13. @ daywithalgorithm Longest Prefix also Suffix Method Longest Prefix also Suffix Method (LPS) is a method to identify the longest prefix of a string, which is also a suffix. 1 2 3 4 5 O N I O N S LETS DECODE THE METHOD

14. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1. Initialize an LPS array with the same length of pattern array and set all index value to 0 1 2 3 4 5 O N I O N S LPS

15. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Inorder to find the prefix which is also a suffix, we are using 2 iterators itr and ctr. Where itr = 0, ctr = 1. Then we will be comparing pattern[itr] and pattern[ctr]. Based on the output we will be updating the values in the LPS array. Itr Ctr Patrn.

16. @ daywithalgorithm Longest Prefix also Suffix Method If Pattern[itr] == Pattern[ctr], then insert LPS[ctr] = ctr. Increment both ctr and itr. 2. If Pattern[itr] != Pattern[ctr], there are two cases. If ctr less than zero, then increment itr. If ctr greater than zero, then set value of ctr to LPS[ctr-1]. LOGIC

17. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Itr Ctr Patrn. Patrn[itr] != Patrn[ctr] and itr == 0. So Increment ctr by 1.

18. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Itr Ctr Patrn. Patrn[itr] != Patrn[ctr] and itr == 0. So Increment ctr by 1.

19. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Itr Ctr 1 Patrn. Patrn[itr] = = Patrn[ctr] and itr == 0. So Increment ctr by 1 and itr by 1 . Set LPS[ctr] = itr

20. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Itr Ctr 1 2 Patrn. Patrn[itr] == Patrn[ctr] and itr == 0. So Increment ctr by 1 and itr by 1. Set LPS[ctr] = itr

21. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 O N I O N S 1 2 3 4 5 LPS Itr Ctr 1 2 Patrn. Patrn[itr] == Patrn[ctr] and itr == 0. So Increment ctr by 1 and itr by 1. Set LPS[ctr] = itr

22. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 LPS 1 2 So now, we have successfully generated the LPS array.

23. @ daywithalgorithm Longest Prefix also Suffix Method 1 2 3 4 5 LPS 1 2 O N I O N I O N S O Text : 1 2 3 4 5 6 7 8 9 Index of Text : O N I O N S Pattern : 1 2 3 4 5 Index of Pattern :

24. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 0 ctr = 0 1 2 3 4 5 LPS 1 2

25. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 1 ctr = 1 1 2 3 4 5 LPS 1 2

26. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 2 ctr = 2 1 2 3 4 5 LPS 1 2

27. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 3 ctr = 3 1 2 3 4 5 LPS 1 2

28. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 4 ctr = 4 1 2 3 4 5 LPS 1 2

29. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 5 1 2 3 4 5 LPS 1 2

30. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 5 1 2 3 4 5 LPS 1 2

31. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 5 1 2 3 4 5 LPS 1 2

32. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 2 1 2 3 4 5 LPS 1 2

33. @ daywithalgorithm O N I O N I O N S O KMP APPROACH 1 2 3 4 5 6 7 8 9 O N I O N S 1 2 3 4 5 itr = 5 ctr = 2 1 2 3 4 5 LPS 1 2

34. KMP APPROACH Best Case Average Case Worst Case O(N + M) O(N + M) O(N) @ daywithalgorithm