    -- |
    -- Module         : Data.ByteString.Search.KnuthMorrisPratt
    -- Copyright      : Justin Bailey
    --                  Chris Kuklewicz
    --                  Daniel Fischer
    -- Licence        : BSD3
    -- Maintainer     : Daniel Fischer <daniel.is.fischer@googlemail.com>
    -- Stability      : Provisional
    -- Portability    : non-portable (BangPatterns)
    --
    -- Fast non-overlapping Knuth-Morris-Pratt search of both strict and
    -- lazy 'Data.ByteString.ByteString' values.
    --
    -- 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.KnuthMorrisPratt
        {-# DEPRECATED "Use the new interface instead" #-}
        (
          -- * Overview
          -- $overview

          -- ** Changes
          -- $changes

          -- ** Deprecation
          -- $deprecation

          -- ** Parameter and return types
          -- $types

          -- ** Lazy ByteStrings
          -- $lazy

          -- * Partial application
          -- $partial

          -- * Complexity and Performance
          -- $complexity

          -- * Functions
          matchLL
        , matchLS
        , matchSS
        , matchSL
        ) where

    import Data.ByteString.Search.Internal.KnuthMorrisPratt
                (matchLL, matchLS, matchSL, matchSS)

    -- $overview
    --
    -- This module exists only for backwards compatibility. Nevertheless
    -- there have been small changes in the behaviour of the functions.
    -- The module exports four search functions: 'matchLL', 'matchLS',
    -- 'matchSL', and 'matchSS'. All of them return the list of all
    -- starting positions of non-overlapping occurrences of a pattern
    -- in a string.

    -- $changes
    --
    -- Formerly, all four functions returned an empty list when passed
    -- an empty pattern. Now, in accordance with the functions from the other
    -- modules, @matchXY \"\" target = [0 .. 'length' target]@.
    --
    -- Further, the return type of 'matchLS' and 'matchSS' has changed to
    -- @['Int']@, since strict 'Data.ByteString.ByteString's are 'Int'-indexed.

    -- $deprecation
    --
    -- This module is /deprecated/. You should use the new interface provided
    -- in "Data.ByteString.Search.KMP" and "Data.ByteString.Lazy.Search.KMP"
    -- or the generally faster functions from "Data.ByteString.Search" and
    -- "Data.ByteString.Search.DFA", respectively the lazy versions.

    -- $types
    --
    -- The first parameter is always the pattern string.  The second
    -- parameter is always the target string to be searched.  The returned
    -- list contains the offsets of all /non-overlapping/ patterns.
    --
    -- A returned @Int@ or @Int64@ is an index into the target string
    -- which is aligned to the head of the pattern string.  Strict targets
    -- return @Int@ indices and lazy targets return @Int64@ indices.  All
    -- returned lists are computed and returned in a lazy fashion.

    -- $lazy
    --
    -- 'matchLL' and 'matchLS' take lazy bytestrings as patterns.  For
    -- performance, if the pattern is not a single strict chunk then all
    -- the the pattern chunks will copied into a concatenated strict
    -- bytestring.  This limits the patterns to a length of (maxBound ::
    -- Int).
    --
    -- 'matchLL' and 'matchSL' take lazy bytestrings as targets.
    -- These are written so that while they work they will not retain a
    -- reference to all the earlier parts of the the lazy bytestring.
    -- This means the garbage collector would be able to keep only a small
    -- amount of the target string and free the rest.

    -- $partial
    --
    -- These functions can all be usefully partially applied. Given only a
    -- pattern, the auxiliary data will be computed only once, allowing for
    -- efficient re-use.

    -- $complexity
    --
    -- The preprocessing of the pattern is /O/(@patternLength@) in time and space.
    -- The time complexity of the searching phase is /O/(@targetLength@) for all
    -- 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" resp. "Data.ByteString.Lazy.Search.DFA".