|
Data.ByteString.Search.KnuthMorrisPratt | Portability | portable | Stability | experimental | Maintainer | Bryan O'Sullivan <bos@serpentine.com> |
|
|
|
|
|
Description |
Fast non-overlapping Knuth-Morris-Pratt search of both strict and
lazy ByteString values.
A description of the algorithm can be found at
http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm.
|
|
Synopsis |
|
|
|
|
Overview
|
|
This module exports 4 search functions: matchLL, matchLS,
matchSL, and matchSS.
If given an empty pattern, a search will always return an empty
list.
|
|
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.
A returned Int or Int64 is an index into the target string
which is aligned to the head of the pattern string. Strict targets
return Int indices and lazy targets return Int64 indices. All
returned lists are computed and returned in a lazy fashion.
|
|
Lazy ByteStrings
|
|
matchLL and 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 ::
Int).
matchLL and 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.
|
|
Functions
|
|
matchLL |
:: ByteString | lazy pattern
| -> ByteString | lazy target string
| -> [Int64] | offsets of matches
|
|
|
matchLS |
:: ByteString | lazy pattern
| -> ByteString | strict target string
| -> [Int64] | offsets of matches
|
|
|
matchSS |
:: ByteString | strict pattern
| -> ByteString | strict target string
| -> [Int64] | offsets of matches
|
|
|
matchSL |
:: ByteString | strict pattern
| -> ByteString | lazy target string
| -> [Int64] | offsets of matches
|
|
|
Produced by Haddock version 0.8 |