Fast search of lazy ByteString values using the Knuth-Morris-Pratt algorithm.

A description of the algorithm can be found at http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm.

Original authors: Justin Bailey (jgbailey at gmail.com) and Chris Kuklewicz (haskell at list.mightyreason.com).

This module provides two functions for finding the occurrences of a pattern in a target string using the Knuth-Morris-Pratt algorithm. It exists mostly for systematic reasons, the functions from Data.ByteString.Lazy.Search are much faster, except for very short patterns or long patterns with a short period if overlap is allowed. In the latter case, indices from this module may be the best choice since the Boyer-Moore function's performance degrades if there are many matches and the DFA function's automaton needs much space for long patterns. In the former case, for some pattern/target combinations DFA has better performance, for others KMP, usually the difference is small.

The preprocessing of the pattern is O(patternLength) in time and space. The time complexity of the searching phase is O(targetLength) for both functions.

In most cases, these functions are considerably slower than the Boyer-Moore variants, performance is close to that of those from Data.ByteString.Search.DFA.

Both functions can be usefully partially applied. Given only a pattern, the auxiliary data will be computed only once, allowing for efficient re-use.