Sunday, September 1, 2013

KMP algorithm

Below there is the C# program which implements the Knuth-Morris-Pratt (KMP) string searching algorithm.
The KMP algorithm searches for occurrences of a pattern P within a text string by employing the observation that when a mismatch occurs, the pattern itself embodies sufficient information to determine where the next match could begin.

KMP spends a little time precomputing a partial match table(on the order of the size of P[], O(p),
and then it uses that table to do an efficient search of the string in O(s), where s is a size of the string.