haskell - 在另一个字符串 Haskell 中查找子字符串的索引

Question

我要制作一个带有两个参数(字符串)的函数。该函数应查看第一个参数是否是第二个参数的子字符串。如果是这种情况，它将返回每个出现的元组，其中包含子字符串的开始索引和子字符串结尾的索引。
例如:

f :: String -> String -> [(Int,Int)]
f "oo" "foobar" = [(1,2)]
f "oo" "fooboor" = [(1,2),(4,5)]
f "ooo" "fooobar" = [(1,3)]

我们不允许导入任何东西，但我有一个 isPrefix 函数。它检查第一个参数是否是第二个参数的前缀。

isPrefix :: Eq a => [a] -> [a] -> Bool 
isPrefix [] _ = True
isPrefix _ [] = False
isPrefix (x:xs) (y:ys) |x== y = isPrefix xs ys
                       |otherwise = False

我在想一个解决方案可能是首先在 x 上运行函数“isPrefix”，如果它返回 False，我就在尾部 (xs) 上运行它，依此类推。但是，我正在努力实现它并努力理解如何返回字符串的索引(如果存在)。也许使用“!!”？你认为我在做什么吗？因为我是 Haskell 的新手，所以语法有点困难:)

Answer 1

我们可以创建一个函数来检查第一个列表是否是第二个列表的前缀。如果是这种情况，我们在前面加上 (0, length firstlist - 1)到递归调用，我们将两个索引都加一。
因此，这意味着这样的函数看起来像:

f :: Eq a => [a] -> [a] -> [(Int, Int)]
f needle = go
  where go [] = []
        go haystack@(_: xs)
            | isPrefix needle haystack = (…, …) : tl  -- (1)
            | otherwise = tl
          where tl = … (go xs)                        -- (2)
        n = length needle

因此，这里 (1) 前置 (…, …)到名单；对于 (2) tl进行递归调用并需要通过将 2-tuple 的两个项目都增加 1 来对列表进行后处理。
有一种更有效的算法来执行此操作，您可以在递归调用中传递当前索引，或者您可以实现 Knuth-Morris-Pratt algorithm [wiki] ，我把这些留作练习。