string - Haskell 程序在字符串中查找子字符串

Question

我想用这种类型签名写一个 Haskell 函数：

findStr :: String -> String -> Maybe Int

findStr pat str将尝试在字符串中查找子pat字符串str。如果成功，它将返回Just n，其中n的位置是patwithin str。

Example:

findStr "abc" "abcdefg" -- returns Just 0

Answer 1

尝试这个：

findStr :: String -> String -> Maybe Int
findStr pat str = findStrHelp pat str 0
  where
    findStrHelp _ [] _ = Nothing
    findStrHelp pat s@(x:xs) n
      | pat == (take (length pat) s) = Just n
      | otherwise = findStrHelp pat xs (n+1)

findStr调用一个帮助函数来跟踪当前索引。findStrHelp然后只需要检查输入的模式是否等于模式长度的下一个子字符串。如果是，则返回Just <index>，否则检查下一个子字符串。如果它遇到一个空列表，它将失败并返回Nothing。

Answer 2

这是另一个解决方案，也使用递归：

findStr :: String -> String -> Maybe Int
findStr sub s
          | length sub > length s      = Nothing
          | take (length sub) s == sub = Just 0
          | otherwise                  = fmap (+1) $ findStr sub $ drop 1 s

有两个终止条件：要么子字符串大于字符串，在这种情况下Nothing返回（并且我们停止递归），或者子字符串匹配字符串的开头，在这种情况下我们停止递归，因为我们有一个匹配项（我们返回Just 0）。

如果没有达到任何终止条件，我们会计算我们所处的位置，并通过删除字符串的第一个字符来递归。

Answer 3

尝试这个：

findStr :: String -> String -> Maybe Int
findStr x y
           | (length $ filtered x y) == 0 = Nothing
           | otherwise = Just $ fst $ head $ filtered x y

filtered :: String -> String -> [(Int, String)]
filtered x y = filter (\(p,q) -> q == x) $ zip [0..(1 + lenY - lenX)] [take lenX $ drop n y | n <- [0..(lenY - lenX)]]
                where lenX = length x
                      lenY = length y

filtered是一个辅助函数，它使用 zip 创建索引的键值对和长度等于 的相应子字符串的列表pat，然后获取匹配的那些对pat。如果上面的列表为空，即没有找到匹配项，或者其中 k 是第一个匹配索引，findStr则返回。NothingJust k