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:
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.
Initialize Variables: Initialize variables
i
andj
to 0.i
represents the index of the main string, andj
represents the index of the pattern string.Iterate through the Main String: While
i
is less than the length of the main string, compare the characters ati
andj
. If they match, increment bothi
andj
. Ifj
reaches the end of the pattern string, a match is found at indexi - j
. Incrementi
andj
accordingly.Handle Mismatch: If the characters at
i
andj
do not match, updatej
using the LPS array and continue comparing.Search Completion: If
j
reaches 0, incrementi
. Ifi
reaches the end of the main string, the search is complete.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.