-- | -- Module : Data.ByteString.Search.KMP -- Copyright : Justin Bailey -- Chris Kuklewicz -- Daniel Fischer -- Licence : BSD3 -- Maintainer : Daniel Fischer <daniel.is.fischer@googlemail.com> -- Stability : Provisional -- Portability : non-portable (BangPatterns) -- -- Fast search of strict 'S.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). module Data.ByteString.Search.KMP ( -- * Overview -- $overview -- ** Complexity and Performance -- $complexity -- ** Partial application -- $partial -- * Functions indices , nonOverlappingIndices ) where import Data.ByteString.Search.Internal.KnuthMorrisPratt (matchSS, indicesS) import qualified Data.ByteString as S -- $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 -- -- 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 -- -- Both functions can be usefully partially applied. Given only a -- pattern, the auxiliary data will be computed only once, allowing for -- efficient re-use. -- | @'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]@. {-# INLINE indices #-} indices :: S.ByteString -- ^ Pattern to find -> S.ByteString -- ^ String to search -> [Int] -- ^ Offsets of matches indices = indicesS -- | @'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'. {-# INLINE nonOverlappingIndices #-} nonOverlappingIndices :: S.ByteString -- ^ Pattern to find -> S.ByteString -- ^ String to search -> [Int] -- ^ Offsets of matches nonOverlappingIndices = matchSS