Search Pattern (KMP Algorithm)

Problem Statement: Given a text txt and a pattern pat, our task is to make a function that searches for all occurrences of pat in txt. The Knuth-Morris-Pratt (KMP) algorithm is one of the efficient ways to solve this problem.

Example 1:

Input: txt = "ababcabcabababd", pat = "ababd"

Output: Pattern found at index 10

Example 2:

Input: txt = "aaaaa", pat = "aa"

Output: Pattern found at index 0

               Pattern found at index 1

                Pattern found at index 2

                Pattern found at index 3

Solution:

The KMP algorithm preprocesses the pattern to create an array lps (Longest Prefix Suffix) that is used to skip unnecessary comparisons in the main search phase.

Steps:

1.    Preprocessing the Pattern to Create LPS Array:

o   The lps array contains the length of the longest proper prefix of the pattern which is also a suffix for every prefix of the pattern.

2.    Pattern Search using the LPS Array:

o   The search phase uses the lps array to skip characters in the text when a mismatch is found.

Time Complexity: O(N + M)

Space Complexity: O(M)