Haskell无导入模块实现子串所有起止索引查询功能（使用自定义isPrefix）

完整可运行代码 #

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

f :: Eq a => [a] -> [a] -> [(Int, Int)]
f pat = go 0
  where
    lenPat = length pat
    -- 辅助函数：第一个参数为当前检查的起始索引，第二个参数为剩余待检查字符串
    go _ [] = []
    go i s@(_:rest)
      -- 剩余字符串长度小于模式串，不可能匹配，直接终止递归
      | length s < lenPat = []
      -- 匹配成功，记录索引后继续检查后续位置
      | isPrefix pat s = (i, i + lenPat - 1) : go (i + 1) rest
      -- 匹配失败，跳到下一个位置检查
      | otherwise = go (i + 1) rest

如果你需要严格匹配题目给出的String专属类型签名，也可以将f的类型声明修改为：

f :: String -> String -> [(Int,Int)]

实现逻辑说明 #

• 不需要使用!!操作符，通过辅助函数go的入参直接跟踪当前检查位置的起始索引，效率更高逻辑更清晰
• 预先计算模式串长度lenPat，避免递归过程中重复计算提升性能
• 每次递归先判断剩余字符串长度是否足够匹配模式串，提前终止无效递归
• 匹配成功时直接计算结束索引（起始索引+模式串长度-1），加入结果列表后继续向后递归查找所有匹配项

测试验证 #

和题目给出的示例完全匹配：

-- 测试1
f "oo" "foobar" = [(1,2)]
-- 测试2
f "oo" "fooboor" = [(1,2),(4,5)]
-- 测试3
f "ooo" "fooobar" = [(1,3)]

内容的提问来源于stack exchange，提问作者Anders Stene