    -- |
    -- Module         : Data.ByteString.Lazy.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 lazy 'L.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.Lazy.Search.KMP (-- * Overview
                                            -- $overview

                                            -- ** Complexity and Performance
                                            -- $complexity

                                            -- ** Partial application
                                            -- $partial

                                            -- * Functions
                                              indices
                                            , nonOverlappingIndices
                                            -- ** Convenience
                                            , strictify
                                            ) where

    import Data.ByteString.Search.Internal.KnuthMorrisPratt (matchSL, indicesL)
    import qualified Data.ByteString as S
    import qualified Data.ByteString.Lazy as L

    import Data.Int (Int64)

    -- $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 mostly for systematic reasons, the functions from
    -- "Data.ByteString.Lazy.Search" are much faster, except for very short
    -- patterns or long patterns with a short period if overlap is allowed.
    -- In the latter case, 'indices' from this module may be the best choice
    -- since the Boyer-Moore function's performance degrades if there are many
    -- matches and the DFA function's automaton needs much space for long
    -- patterns.
    -- In the former case, for some pattern\/target combinations DFA has better
    -- performance, for others KMP, usually the difference is small.

    -- $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     -- ^ Strict pattern to find
            -> L.ByteString     -- ^ Lazy string to search
            -> [Int64]          -- ^ Offsets of matches
    indices :: ByteString -> ByteString -> [Int64]
    indices = ByteString -> ByteString -> [Int64]
    indicesL

    -- | @'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   -- ^ Strict pattern to find
                          -> L.ByteString   -- ^ Lazy string to search
                          -> [Int64]        -- ^ Offsets of matches
    nonOverlappingIndices :: ByteString -> ByteString -> [Int64]
    nonOverlappingIndices = ByteString -> ByteString -> [Int64]
    matchSL

    -- | @'strictify'@ transforms a lazy 'L.ByteString' into a strict
    --   'S.ByteString', to make it a suitable pattern for the searching
    --   functions.
    strictify :: L.ByteString -> S.ByteString
    strictify :: ByteString -> ByteString
    strictify = [ByteString] -> ByteString
    S.concat ([ByteString] -> ByteString)
    -> (ByteString -> [ByteString]) -> ByteString -> ByteString
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ByteString -> [ByteString]
    L.toChunks