-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Knuth–Morris–Pratt string searching algorithm
--   
--   This module implements the Knuth-Morris-Pratt algorithm. It can search
--   a word in a text in O(m+n) time, where m and n are the length of the
--   word and the text. This module can apply on any list of instance of
--   Eq.
@package KMP
@version 0.1


-- | This module implements the Knuth-Morris-Pratt algorithm. It can search
--   a word in a text in O(m+n) time, where m and n are the length of the
--   word and the text.
--   
--   This module can apply on any list of instance of Eq.
--   
--   Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). Fast pattern
--   matching in strings. SIAM Journal on Computing 6 (2): 323–350.
--   doi:10.1137/0206024
--   
--   Sample usage:
--   
--   <pre>
--   let
--     word = <a>abababcaba</a>
--     text = <a>abababababcabababcababbb</a>
--     kmpTable = build word
--     result = match kmpTable text
--     -- the <tt>result</tt> should be [4, 11]
--   </pre>
module Data.Algorithms.KMP

-- | The solid data type of KMP table
data Table a

-- | The <a>build</a> function eats a pattern (list of some Eq) and
--   generates a KMP table.
--   
--   The time and space complexities are both O(length of the pattern)
build :: Eq a => [a] -> Table a

-- | The <a>match</a> function takes the KMP table and a list to be
--   searched (might be infinite) and then generates the search results as
--   a list of every matched begining (might be infinite).
--   
--   The time complexity is O(length of the pattern + length of the
--   searched list)
match :: Eq a => Table a -> [a] -> [Int]