HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduletext-2.1.3Haskell2010

Data.Text.Internal.Search

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

  • 1 value
  • Packagetext-2.1.3
  • Exports1
  • LanguageHaskell2010
  • LicenceBSD-2-Clause
  • SourceSearch.hs
valueindices
  1. :: Text

    Substring to search for (needle)

  2. -> Text

    Text to search in (haystack)

  3. -> [Int]
#

O(n+m) Find the offsets of all non-overlapping indices of needle within haystack.

In (unlikely) bad cases, this algorithm's complexity degrades towards O(n*m).