在Data/ByteString.hs
的源代码中说,不赞成使用findSubstrings
函数,而推荐使用breakSubstring
。但是,我认为使用KMP算法实现的findSubstrings
比幼稚的breakSubstring
中使用的算法高效得多。有人知道为什么要这样做吗?
这是旧的实现:
{-# DEPRECATED findSubstrings "findSubstrings is deprecated in favour of breakSubstring." #-}
{-
{- This function uses the Knuth-Morris-Pratt string matching algorithm. -}
findSubstrings pat@(PS _ _ m) str@(PS _ _ n) = search 0 0
where
patc x = pat `unsafeIndex` x
strc x = str `unsafeIndex` x
-- maybe we should make kmpNext a UArray before using it in search?
kmpNext = listArray (0,m) (-1:kmpNextL pat (-1))
kmpNextL p _ | null p = []
kmpNextL p j = let j' = next (unsafeHead p) j + 1
ps = unsafeTail p
x = if not (null ps) && unsafeHead ps == patc j'
then kmpNext Array.! j' else j'
in x:kmpNextL ps j'
search i j = match ++ rest -- i: position in string, j: position in pattern
where match = if j == m then [(i - j)] else []
rest = if i == n then [] else search (i+1) (next (strc i) j + 1)
next c j | j >= 0 && (j == m || c /= patc j) = next c (kmpNext Array.! j)
| otherwise = j
-}
这是新的天真:
findSubstrings :: ByteString -- ^ String to search for.
-> ByteString -- ^ String to seach in.
-> [Int]
findSubstrings pat str
| null pat = [0 .. length str]
| otherwise = search 0 str
where
STRICT2(search)
search n s
| null s = []
| pat `isPrefixOf` s = n : search (n+1) (unsafeTail s)
| otherwise = search (n+1) (unsafeTail s)
最佳答案
进行更改的原因是,KMP的实现实际上比幼稚的版本效率低,而幼稚的版本只是着眼于性能。
关于haskell - Data.ByteString中的findSubstrings和breakSubstring,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6331269/