| ||||||||

| ||||||||

| ||||||||

Description | ||||||||

Fast overlapping Boyer-Moore search of both strict and lazy
Descriptions of the algorithm can be found at http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm Original authors: Daniel Fischer (daniel.is.fischer at web.de) and Chris Kuklewicz (haskell at list.mightyreason.com). | ||||||||

Synopsis | ||||||||

| ||||||||

Overview | ||||||||

This module exports 4 search functions: 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 A returned | ||||||||

Lazy ByteStrings | ||||||||

| ||||||||

Performance | ||||||||

Operating on a strict target string is faster than a lazy target string. It is unclear why the performance gap is as large as it is (patches welcome). To slightly ameliorate this, if the lazy string is a single chunk then a copy of the strict algorithm is used. | ||||||||

Complexity | ||||||||

Preprocessing the pattern string is O(patternLength). The search
performance is O(targetLength/patternLength) in the best case,
allowing it to go faster than a Knuth-Morris-Pratt algorithm. With
a non-periodic pattern the worst case uses O(3*targetLength)
comparisons. The periodic pattern worst case is quadratic
O(targetLength*patternLength) complexity. Improvements
(e.g. Turbo-Boyer-Moore) to catch and linearize worst case
performance slow down the loop significantly.
| ||||||||

Currying | ||||||||

These functions can all be usefully curried. Given only a pattern
the curried version will compute the supporting lookup tables only
once, allowing for efficient re-use. Similarly, the curried
matchLL and matchLS will compute the concatenated pattern only
once.
| ||||||||

Integer overflow | ||||||||

The current code uses Int to keep track of the locations in the
target string. If the length of the pattern plus the length of any
strict chunk of the target string is greater or equal to
then this will overflow causing an error. We try
to detect this and call maxBound::Interror before a segfault occurs.
| ||||||||

Functions | ||||||||

matchLL | ||||||||

| ||||||||

matchLS | ||||||||

| ||||||||

matchSL | ||||||||

| ||||||||

matchSS | ||||||||

| ||||||||

Produced by Haddock version 0.8 |