KMP 0.1.0.1 → 0.1.0.2

raw patch · 4 files changed

+68/−19 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Changes +9/−0
• KMP.cabal +2/−1
• src/Data/Algorithms/KMP.hs +25/−11
• testsuite/tests/Data/Algorithms/KMP/Main.hs +32/−7

@@ -0,0 +1,9 @@+0.1.0.2         2012.3.5+                Reimplement the real KMP version, instead of the MP version.+                Thank MaskRay from #haskell for noticing.++0.1.0.1         2012.3.4+                Haddock fix++0.1             2012.3.2+                First version

@@ -6,7 +6,7 @@ -- 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.0.1+Version:             0.1.0.2  -- A short (one-line) description of the package. Synopsis:            Knuth–Morris–Pratt string searching algorithm@@ -49,6 +49,7 @@ -- a README. Extra-source-files:     README,+    Changes,     testsuite/tests/Data/Algorithms/KMP/Main.hs  -- Constraint on the version of Cabal needed to build this package.

@@ -47,22 +47,38 @@      resTable = Table       { alphabetTable = listArray (0,len-1) pattern-      , jumpTable = listArray (0,len-1) $ -1 : map genJump [1..]+      , jumpTable = listArray (-1,len-1) $ (-2) : genJump (-1) 0       } -    genJump i =+    genJump _ 0 =       let+        o = if 1 == len || alphabetTable resTable ! 0 /= alphabetTable resTable ! 1+          then -1+          else -2++        later = genJump (-1) 1+      in+        o : later++    genJump lastMPJump i =+      let         ch = alphabetTable resTable ! i          findJ j-          | alphabetTable resTable ! (j + 1) == ch = j-          | j == (-1) = -2+          | j == -2 = -2+          | alphabetTable resTable ! (j+1) == ch = j+          | j == -1 = -2           | otherwise = findJ (jumpTable resTable ! j) -        j = findJ ( jumpTable resTable ! (i-1) )-      in-        j + 1+        j = findJ lastMPJump +        o = if i+1 == len || alphabetTable resTable ! (i+1) /= alphabetTable resTable ! (j+2)+          then j+1+          else jumpTable resTable ! (j+1)++        later = genJump (j+1) (i+1)+      in o : later+   in     resTable @@ -81,9 +97,8 @@           (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)+                | j < 0 || j < len && s == alphabetTable table ! j = (i + 1, j + 1, ss)+                | otherwise = (i, 1 + (jumpTable table ! (j - 1)), str)             in               go i' j' str'           _ -> []@@ -93,4 +108,3 @@           else later   in     go 0 0 str-

@@ -12,14 +12,39 @@   , exitSuccess   ) -main = do+import Control.Monad+  ( foldM+  )++check word text =   let-    pattern = "abababcaba"-    target = cycle "abababababcabababcababbb"-    table = build pattern-    res1 = take 100 $ match table target-    res2 = take 100 $ findIndices (isPrefixOf pattern) (tails target)+    table = build word+    res1 = match table text+    res2 = findIndices (isPrefixOf word) (tails text)+  in take 100 res1 == take 100 res2 -  if res1 == res2+dataset =+  [ ("abababcaba", "abababababcabababcababbb")+  , ("ababcabababc", "ababcabababcabababc")+  , ("ababcabababc", cycle "ababcabababcabababc")+  , ("", "abca")+  , ("abca", "")+  ]++main = do+  res <- foldM+    ( \res (word, text) -> do+      if check word text+        then return res+        else do+          putStrLn "Failed dataset:"+          putStrLn $ "  " ++ word+          putStrLn $ "  " ++ take 100 text ++ if null (drop 100 text) then "" else "..."+          return False+    )+    True+    dataset++  if res     then exitSuccess     else exitFailure