Portability | non-portable (BangPatterns) |
---|---|

Stability | Provisional |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

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).

- 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

:: ByteString | Pattern to find |

-> ByteString | String 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]

:: ByteString | Pattern to find |

-> ByteString | String 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`

.