kmp algorithm c++

KMP Algorithm in C++

The Knuth-Morris-Pratt (KMP) algorithm is used for pattern searching in strings. It is an efficient algorithm that avoids unnecessary comparisons by utilizing the information about the previous matches. Here are the steps of the KMP algorithm:

  1. Create LPS Array: Create a Longest Proper Prefix which is also a Suffix (LPS) array that stores the length of the longest proper prefix that is also a suffix for each pattern substring.

  2. Initialize Variables: Initialize variables i and j to 0. i represents the index of the main string, and j represents the index of the pattern string.

  3. Iterate through the Main String: While i is less than the length of the main string, compare the characters at i and j. If they match, increment both i and j. If j reaches the end of the pattern string, a match is found at index i - j. Increment i and j accordingly.

  4. Handle Mismatch: If the characters at i and j do not match, update j using the LPS array and continue comparing.

  5. Search Completion: If j reaches 0, increment i. If i reaches the end of the main string, the search is complete.

  6. Search Result: The algorithm returns the indices of all occurrences of the pattern in the main string.

The KMP algorithm's efficiency lies in the fact that it avoids unnecessary backtracking by utilizing the information from the LPS array, making it more efficient than naive string matching algorithms.