有没有更好的方法来编写“string contains 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 的 /a> 肯定会解决问题，但是如果遇到更长的干草堆或反常的针，您应该考虑更高级的字符串匹配算法具有更好的平均和最坏情况复杂度。

---

1 考虑一个非常长的字符串，仅由 a 和一根开头有很多 a 的针组成，最后有一个 b结束。

Answer 3

考虑使用 text 包(text 在 Hackage 上，现在也是 Haskell Platform 的一部分），满足您的文本处理需求。它提供了 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