stringsearch-0.3.0: Fast searching, splitting and replacing of ByteStringsSource codeContentsIndex
Data.ByteString.Search.KMP
Portabilitynon-portable (BangPatterns)
StabilityProvisional
MaintainerDaniel Fischer <daniel.is.fischer@web.de>
Contents
Overview
Complexity and Performance
Partial application
Functions
Description

Fast search of strict 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).

Synopsis
indices :: ByteString -> ByteString -> [Int]
nonOverlappingIndices :: ByteString -> ByteString -> [Int]
Overview
This module provides two functions for finding the occurrences of a pattern in a target string using the Knuth-Morris-Pratt algorithm. It exists only for systematic reasons, the functions from Data.ByteString.Search are much faster, except for very short patterns, in which case Data.ByteString.Search.DFA provides better functions.
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 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.

Partial application
Both functions can be usefully partially applied. Given only a pattern, the auxiliary data will be computed only once, allowing for efficient re-use.
Functions
indicesSource
:: ByteStringPattern to find
-> ByteStringString to search
-> [Int]Offsets of matches
indices finds the starting indices of all possibly overlapping occurrences of the pattern in the target string. If the pattern is empty, the result is [0 .. length target].
nonOverlappingIndicesSource
:: ByteStringPattern to find
-> ByteStringString to search
-> [Int]Offsets of matches
nonOverlappingIndices finds the starting indices of all non-overlapping occurrences of the pattern in the target string. It is more efficient than removing indices from the list produced by indices.
Produced by Haddock version 2.4.2