在另一个字符串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

我在想一个解决方案可能是运行函数"isPrefix"首先在x上运行，如果返回False，则在尾部(xs)上运行，以此类推。然而，我正在努力实现它，并努力理解如何返回字符串的索引，如果它存在。也许用"!! !"你觉得我说对了什么吗?由于我是Haskell的新手，语法有点困难:)

Answer 1

我们可以编写一个函数来检查第一个列表是否为第二个列表的前缀。如果是这种情况，我们将(0, length firstlist - 1)添加到递归调用中，并将两个索引都增加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元组的两个元素都加1来后处理列表。

有一个更有效的算法可以做到这一点，你在递归调用中传递当前索引，或者你可以实现Knuth-Morris-Pratt算法[wiki]，我把这些留作练习。