官术网_书友最值得收藏!

Searching for a substring using Data.ByteString

There are many algorithms to search for a string within another string. This recipe will use an existing breakSubstring function in the Data.ByteString library to do most of the heavy lifting.

The ByteString documentation establishes its merits by declaring the following claim:

"[A ByteString is] a time- and space-efficient implementation of byte vectors using packed Word8 arrays, suitable for high performance use, both in terms of large data quantities, or high speed requirements. Byte vectors are encoded as strict Word8 arrays of bytes, held in a ForeignPtr, and can be passed between C and Haskell with little effort."

More information and documentation can be obtained on the package web page at http://hackage.haskell.org/package/bytestring/docs/Data-ByteString.html.

How to do it...

  1. Import the breakSubstring function as well as the Data.ByteString.Char8 package as follows:
    import Data.ByteString (breakSubstring)
    import qualified Data.ByteString.Char8 as C
  2. Pack the strings as a ByteString and feed them into breakSubstring which has the following type: ByteString -> ByteString -> (ByteString, ByteString). Then determine whether the string is found:
    substringFound :: String -> String -> Bool
    
    substringFound query str = 
      (not . C.null . snd) $ 
      breakSubstring (C.pack query) (C.pack str)
  3. Try out some tests in main as follows:
    main = do
      print $ substringFound "scraf" "swedish scraf mafia"
      print $ substringFound "flute" "swedish scraf mafia"
  4. Executing main will print out the following results:
    True
    False
    

How it works...

The breakSubstring function recursively checks if the pattern is a prefix of the string. To lazily find the first occurrence of a string, we can call snd (breakSubstring pat str).

There's more...

Another elegant way to quickly find a substring is by using the isInfixOf function provided by both Data.List and Data.ByteString. Moreover, we can also use the OverloadedStrings language extension to remove verbiage, as shown in the following code snippet:

{-# LANGUAGE OverloadedStrings #-}
import Data.ByteString (isInfixOf)

main = do
  print $ isInfixOf "scraf" "swedish scraf mafia"
  print $ isInfixOf "flute" "swedish scraf mafia"

See also

Depending on the length of the pattern we're trying to find and the length of the whole string itself, other algorithms may provide better performance. Refer to the Searching a string using the Boyer-Moore-Horspool algorithm and Searching a string using the Rabin-Karp algorithm recipes for more details.

主站蜘蛛池模板: 永德县| 外汇| 汉中市| 阿拉善右旗| 海兴县| 平果县| 同江市| 铜鼓县| 青铜峡市| 独山县| 台东市| 旅游| 克拉玛依市| 旌德县| 绥阳县| 常州市| 盐边县| 民勤县| 大埔区| 灵石县| 驻马店市| 泊头市| 灵石县| 永城市| 永州市| 龙陵县| 新余市| 万载县| 新绛县| 孟津县| 平利县| 城步| 岑巩县| 宜兴市| 化德县| 灵武市| 南开区| 柏乡县| 金坛市| 汽车| 保德县|