W3cubDocs

/Haskell 8

Data.Text.Internal.Search

Copyright (c) Bryan O'Sullivan 2009
License BSD-style
Maintainer [email protected]
Stability experimental
Portability GHC
Safe Haskell None
Language Haskell2010

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)

indices Source

Arguments

:: Text

Substring to search for (needle)
-> Text

Text to search in (haystack)
-> [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).

© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/8.8.3/docs/html/libraries/text-1.2.4.0/Data-Text-Internal-Search.html