KMP (empty) → 0.1

raw patch · 6 files changed

+250/−0 lines, 6 filesdep +Cabaldep +KMPdep +arraysetup-changed

Dependencies added: Cabal, KMP, array, base

Files

KMP.cabal +79/−0
LICENSE +30/−0
README +18/−0
Setup.hs +2/−0
src/Data/Algorithms/KMP.hs +96/−0
testsuite/tests/Data/Algorithms/KMP/Main.hs +25/−0

+ KMP.cabal view

@@ -0,0 +1,79 @@+-- KMP.cabal auto-generated by cabal init. For additional options, see+-- http://www.haskell.org/cabal/release/cabal-latest/doc/users-guide/authors.html#pkg-descr.+-- The name of the package.+Name:                KMP++-- The package version. See the Haskell package versioning policy+-- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for+-- standards guiding when and how versions should be incremented.+Version:             0.1++-- A short (one-line) description of the package.+Synopsis:            Knuth–Morris–Pratt string searching algorithm++-- A longer description of the package.+Description:         +    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.++-- URL for the project homepage or repository.+Homepage:            https://github.com/CindyLinz/Haskell-KMP++-- The license under which the package is released.+License:             BSD3++-- The file containing the license text.+License-file:        LICENSE++-- The package author(s).+Author:              Cindy Wang (CindyLinz)++-- An email address to which users can send suggestions, bug reports,+-- and patches.+Maintainer:          Cindy Wang <cindylinz@gmail.com>++-- A copyright notice.+Copyright:           2012, Cindy Wang (CindyLinz)++Category:            Algorithms++Stability:           alpha++Build-type:          Simple++Tested-with:         GHC == 7.0.4++-- Extra files to be distributed with the package, such as examples or+-- a README.+Extra-source-files:+    README,+    testsuite/tests/Data/Algorithms/KMP/Main.hs++-- Constraint on the version of Cabal needed to build this package.+Cabal-version:       >= 1.9.2++Library+  hs-source-dirs:      src+  -- Modules exported by the library.+  Exposed-modules:     Data.Algorithms.KMP+  +  -- Packages needed in order to build this package.+  Build-depends:       base >= 3.0 && < 5,+                       array >= 0.3 && < 1+  +  -- Modules not exported by this package.+  -- Other-modules:       +  +  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.+  -- Build-tools:         +  +Test-Suite test+  type:                exitcode-stdio-1.0+  main-is:             Main.hs+  hs-source-dirs:      testsuite/tests/Data/Algorithms/KMP+  build-depends:       base >= 3.0 && < 5,+                       Cabal >= 1.9.2,+                       KMP+

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c)2012, Cindy Wang (CindyLinz)++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Cindy Wang (CindyLinz) nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ README view

@@ -0,0 +1,18 @@+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:++> let+>   word = "abababcaba"+>   text = "abababababcabababcababbb"+>   kmpTable = build word+>   result = match kmpTable text+>   -- the 'result' should be [4, 11]+

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ src/Data/Algorithms/KMP.hs view

@@ -0,0 +1,96 @@+-- |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:+--+-- @+--  let+--    word = "abababcaba"+--    text = "abababababcabababcababbb"+--    kmpTable = build word+--    result = match kmpTable text+--    -- the 'result' should be [4, 11]+-- @+--+module Data.Algorithms.KMP+  ( Table+  , build+  , match+  ) where++import Data.Array+  ( Array+  , listArray+  , bounds+  , (!)+  )++-- |The solid data type of KMP table+data Table a = Table+  { alphabetTable :: Array Int a+  , jumpTable :: Array Int Int+  }++-- |The 'build' 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+build pattern =+  let+    len = length pattern++    resTable = Table+      { alphabetTable = listArray (0,len-1) pattern+      , jumpTable = listArray (0,len-1) $ -1 : map genJump [1..]+      }++    genJump i =+      let+        ch = alphabetTable resTable ! i++        findJ j+          | alphabetTable resTable ! (j + 1) == ch = j+          | j == (-1) = -2+          | otherwise = findJ (jumpTable resTable ! j)++        j = findJ ( jumpTable resTable ! (i-1) )+      in+        j + 1++  in+    resTable++-- |The 'match' 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]+match table str =+  let+    len = 1 + snd ( bounds (alphabetTable table) )++    go i j str =+      let+        later = case str of+          (s:ss) ->+            let+              (i', j', str')+                | j < len && s == alphabetTable table ! j = (i + 1, j + 1, ss)+                | j > 0 = (i, 1 + (jumpTable table ! (j - 1)), str)+                | otherwise = (i + 1, 0, ss)+            in+              go i' j' str'+          _ -> []+      in+        if j == len+          then i-len : later+          else later+  in+    go 0 0 str+

+ testsuite/tests/Data/Algorithms/KMP/Main.hs view

@@ -0,0 +1,25 @@+module Main where++import Data.Algorithms.KMP+import Data.List+  ( findIndices+  , isPrefixOf+  , tails+  )++import System.Exit+  ( exitFailure+  , exitSuccess+  )++main = do+  let+    pattern = "abababcaba"+    target = cycle "abababababcabababcababbb"+    table = build pattern+    res1 = take 100 $ match table target+    res2 = take 100 $ findIndices (isPrefixOf pattern) (tails target)++  if res1 == res2+    then exitSuccess+    else exitFailure