如何在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的新手，语法有些难以理解 :)

- Anders Stene

---

不要使用 !!。相反，对第二个字符串进行递归处理。如果 f "oo" "foobar" 的结果是 [(1,2)]，如何更改该列表以获得 f "oo" "ofoobar" 的正确结果？f "oo" "oofoobar" 呢？考虑如何重复使用尾部的结果以获得一个字符更长的字符串的结果。使用 map 可能有帮助，还可以使用 isPrefix。 - chi

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元组的两个项目都加一来进行后处理。

有一种更有效的算法可以在递归调用中传递当前索引，或者您可以实现Knuth-Morris-Pratt算法[维基百科]，我把它们留作练习。

- Willem Van Onsem