{"id":17471,"date":"2023-08-03T09:46:58","date_gmt":"2023-08-03T09:46:58","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=17471"},"modified":"2023-08-03T09:46:58","modified_gmt":"2023-08-03T09:46:58","slug":"kmp-algorithm-for-pattern-searching","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/kmp-algorithm-for-pattern-searching\/","title":{"rendered":"KMP Algorithm for Pattern Searching"},"content":{"rendered":"

\"\"<\/p>\n

The KnuthMorrisPratt, KMP algorithm is a linear time string matching technique developed by Donald Knuth, Vaughan Pratt, and James H. Morris. It deals with the problem of locating instances of a pattern ‘p’ within a larger string ‘S.’ By avoiding unnecessary comparisons with elements of ‘S’ that have already been involved in comparisons with the pattern ‘p,’ the algorithm achieves a matching time complexity of O(n). This eliminates the need for backtracking on the string ‘S’ and improves efficiency significantly.<\/p>\n

Components of the KMP Algorithm<\/h2>\n

1. The Prefix Function (\u03a0)<\/strong>
\nThe prefix function, denoted as, contains information about how the pattern ‘p’ matches its shifted versions. This information is critical for avoiding redundant pattern shifts during the matching process, which prevents backtracking on the string ‘S.’<\/p>\n

2. The KMP Matcher<\/strong>
\nThe KMP Matcher uses ‘S,’ ‘p,’ and the prefix function ” as inputs to find occurrences of ‘p’ in ‘S’ and returns the number of shifts of ‘p’ required to find these occurrences.<\/p>\n

The Prefix Function (\u03a0)<\/h2>\n

The prefix function is computed using the following pseudocode:<\/p>\n

\"\"<\/p>\n

The running time analysis reveals that the prefix function takes O(m) time to compute, where m is the length of the pattern ‘p.’<\/p>\n

String Matching of KMP Algorithm<\/h2>\n

We will look at an example of how the KMP algorithm works in the case of string matching patterns.<\/p>\n

Problem Statement<\/strong>
\nWrite a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[] given a text txt[0… N1] and a pattern pat[0… M1]. You may assume that N > M.<\/p>\n

For example:<\/strong>
\ntxt = \u201cAABACDEFG\u201d and pat = \u201cAABA\u201d<\/p>\n

Output<\/strong>
\nPattern found at index 0<\/p>\n

Algorithm for KMP Algorithm<\/h2>\n
    \n
  1. \n

    Preprocessing (Building the LPS array):
    \nCreate an array LPS (Longest Prefix Suffix) of size n (length of the pattern).
    \nInitialize two pointers, i and j, where i starts from 0 and j starts from 1.<\/p>\n<\/li>\n

  2. \n

    Building the LPS array:
    \nSet LPS[0] to 0 since there is no proper prefix or suffix for a single character.
    \nRepeat the following steps while j < n:
    \nIf pattern[i] == pattern[j], set LPS[j] = i + 1, increment both i and j.
    \nIf pattern[i]!= pattern[j]:
    \nIf i is not at the beginning (i > 0), set i = LPS[i1].
    \nIf i is at the beginning (i = 0), set LPS[j] = 0, increment j.<\/p>\n<\/li>\n

  3. \n

    Pattern Matching:
    \nInitialize two pointers, i (index for the text) and j (index for the pattern), both starting from 0.
    \nRepeat the following steps while i < m (length of the text) and j < n (length of the pattern):
    \nIf text[i] == pattern[j], increment both i and j.
    \nIf j == n, a match is found at index i j in the text, and j = LPS[j1].
    \nIf text[i]!= pattern[j]:
    \nIf j is not at the beginning (j > 0), set j = LPS [j1].
    \nIf j is at the beginning (j = 0), increment i.<\/p>\n<\/li>\n

  4. \n

    Repeat step 3 until i reach the end of the text or a match is found.<\/p>\n<\/li>\n<\/ol>\n

    The KMP algorithm optimizes pattern matching by utilizing the information in the LPS array, which represents the longest proper prefix of the pattern that is also a proper suffix. This allows the algorithm to avoid unnecessary comparisons during the search, making it more efficient than naive pattern matching algorithms.<\/p>\n

    Code Implementation of KMP Algorithm<\/h3>\n\t\t\t\t\t\t\t

    Code Implementation of KMP Algorithm <\/h3>\r\n\t\t\t\t\t\t\t\t