
Day-19: Knuth-Morris-Pratt Algorithm(KMP)
KMP is a very famous string searching algorithm.
The algorithm, takes a text and a pattern to search in the text.
What makes KMP special is that it computes a failure function which basically tells the program where to move next.
Preprocessing takes O(m) time where m is the length of the pattern.
Time complexity: O(n+m) (May take up to O(mn) when the pattern is so “inconvenient”. e.g “xaaaaaaaaaaaaaa”)
Here is the link of my C++ implementation of KMP: Knuth-Morris-Pratt Algorithm