有没有更好的方法来编写"字符串包含X"方法？

Question

只是盯着使用Haskell并实现(据我所知),没有直接的方法来检查字符串,看它是否包含一个较小的字符串.所以我想我只是试一试.

基本上,我们的想法是检查两个字符串是否大小相同并且相等.如果检查的字符串较长,则递归地删除头部并再次运行检查,直到检查的字符串长度相同.

其余的可能性我使用模式匹配来处理它们.这就是我想出的:

stringExists "" wordToCheckAgainst = False
stringExists wordToCheckFor "" = False
stringExists wordToCheckFor wordToCheckAgainst | length wordToCheckAgainst < length wordToCheckFor = False
                                               | length wordToCheckAgainst == length wordToCheckFor = wordToCheckAgainst == wordToCheckFor
                                               | take (length wordToCheckFor) wordToCheckAgainst == wordToCheckFor = True
                                               | otherwise = stringExists wordToCheckFor (tail wordToCheckAgainst)

Answer 1

如果你在Hoogle中搜索你正在寻找的功能的签名(String -> String -> Bool),你应该看到isInfixOf最好的结果.

Answer 2

isInfixOf从Data.List一定会解决这个问题,但是在更长的草堆或perverse¹针的情况下,你应该考虑更高级的字符串匹配算法有一个更好的平均和最坏情况的复杂性.

¹考虑一个非常长的字符串,只包含a's'和一个针头,a开头有很多,最后一针b.

Answer 3

考虑使用text软件包(text在Hackage上,现在也是Haskell平台的一部分)来满足您的文本处理需求.它提供Unicode文本类型,比基于内置列表的更加节省时间和空间String.对于字符串搜索,该text软件包实现了一种基于Boyer-Moore的算法,该算法比使用的天真方法具有更好的复杂性Data.List.isInfixOf.

用法示例:

Prelude> :s -XOverloadedStrings
Prelude> import qualified Data.Text as T
Prelude Data.Text> T.breakOnAll "abc" "defabcged"
[("def","abcged")]
Prelude Data.Text> T.isInfixOf "abc" "defabcged"
True