|Maintainer||Daniel Fischer <firstname.lastname@example.org>|
Deprecated: Use the new interface instead
Fast non-overlapping Knuth-Morris-Pratt search of both strict and
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 exists only for backwards compatibility. Nevertheless
there have been small changes in the behaviour of the functions.
The module exports four search functions:
matchSS. All of them return the list of all
starting positions of non-overlapping occurrences of a pattern
in a string.
Formerly, all four functions returned an empty list when passed
an empty pattern. Now, in accordance with the functions from the other
matchXY "" target = [0 .. .
This module is deprecated. You should use the new interface provided in Data.ByteString.Search.KMP and Data.ByteString.Lazy.Search.KMP or the generally faster functions from Data.ByteString.Search and Data.ByteString.Search.DFA, respectively the lazy versions.
Parameter and return types
The first parameter is always the pattern string. The second parameter is always the target string to be searched. The returned list contains the offsets of all non-overlapping patterns.
Int64 is an index into the target string
which is aligned to the head of the pattern string. Strict targets
Int indices and lazy targets return
Int64 indices. All
returned lists are computed and returned in a lazy fashion.
matchLS take lazy bytestrings as patterns. For
performance, if the pattern is not a single strict chunk then all
the the pattern chunks will copied into a concatenated strict
bytestring. This limits the patterns to a length of (maxBound ::
matchSL take lazy bytestrings as targets.
These are written so that while they work they will not retain a
reference to all the earlier parts of the the lazy bytestring.
This means the garbage collector would be able to keep only a small
amount of the target string and free the rest.
These functions can all be usefully partially applied. Given only a pattern, the auxiliary data will be computed only once, allowing for efficient re-use.
Complexity and Performance
The preprocessing of the pattern is O(
patternLength) in time and space.
The time complexity of the searching phase is O(
targetLength) for all