stringsearch-0.1ContentsIndex
Data.ByteString.Search.KnuthMorrisPratt
Portabilityportable
Stabilityexperimental
MaintainerBryan O'Sullivan <bos@serpentine.com>
Contents
Overview
Parameter and return types
Lazy ByteStrings
Functions
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
matchLL :: ByteString -> ByteString -> [Int64]
matchLS :: ByteString -> ByteString -> [Int64]
matchSS :: ByteString -> ByteString -> [Int64]
matchSL :: ByteString -> ByteString -> [Int64]
Overview
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
:: ByteStringlazy pattern
-> ByteStringlazy target string
-> [Int64]offsets of matches
matchLS
:: ByteStringlazy pattern
-> ByteStringstrict target string
-> [Int64]offsets of matches
matchSS
:: ByteStringstrict pattern
-> ByteStringstrict target string
-> [Int64]offsets of matches
matchSL
:: ByteStringstrict pattern
-> ByteStringlazy target string
-> [Int64]offsets of matches
Produced by Haddock version 0.8