| Copyright | (c) Bryan O'Sullivan 2009 |
|---|---|
| License | BSD-style |
| Maintainer | bos@serpentine.com |
| Stability | experimental |
| Portability | GHC |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Text.Internal.Search
Description
Fast substring search for
Text
, based on work by Boyer, Moore,
Horspool, Sunday, and Lundh.
References:
- R. S. Boyer, J. S. Moore: A Fast String Searching Algorithm. Communications of the ACM, 20, 10, 762-772 (1977)
- R. N. Horspool: Practical Fast Searching in Strings. Software - Practice and Experience 10, 501-506 (1980)
- D. M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)
- F. Lundh: The Fast Search Algorithm. http://effbot.org/zone/stringlib.htm (2006)
Documentation
Arguments
| :: Text |
Substring to search for (
|
| -> Text |
Text to search in (
|
| -> [ Int ] |
O(n+m)
Find the offsets of all non-overlapping indices of
needle
within
haystack
. The offsets returned represent
uncorrected indices in the low-level "needle" array, to which its
offset must be added.
In (unlikely) bad cases, this algorithm's complexity degrades towards O(n*m) .