1

我需要一个函数来查找字符串中子字符串的所有索引。您可以在下面找到我的代码，但我只是想知道是否有更好的方法：

-- find index of substring in string
--      index_of_substring "so" "unsomesome" -> Just 2
--      index_of_substring "to" "unsomesome" -> Nothing
index_of_substring :: String -> String -> Maybe Int
index_of_substring _ []  = Nothing
index_of_substring sub str = case List.isPrefixOf sub str of
    False -> fmap (+1) $ index_of_substring sub (tail str)
    True  -> Just 0

-- find all occurences of pattern in a string
--      all_occurrences_of_pattern_in_string "so" "unsomesomesome" -> [2,6,10]
all_occurrences_of_pattern_in_string pattern s = helper pattern s [] 0
    where helper pattern s result last_idx = case index_of_substring pattern s of
            Just n -> helper pattern (drop (n + 1) s) (result ++ [n + last_idx]) (last_idx + n + 1)
            Nothing -> result
4

1 回答 1

0

我会说它至少可以做得更简单。除非重点是从头开始编写自己的算法（我不认为是这种情况，因为您正在使用Data.List.isPrefixOf），否则您可以简单地利用Data.List.elemIndices来缩短您必须执行的检查次数：

indicesOfSubStr :: String -> String -> [Int]
indicesOfSubStr []  _   = []
indicesOfSubStr sub str = filter (\i -> sub `isPrefixOf` drop i str) $ head sub `elemIndices` str

indexOfSubStr :: String -> String -> Maybe Int
indexOfSubStr = listToMaybe .: indicesOfSubStr where (.:) = (.) . (.)

所以在这里我elemIndices用来获取 in 的第一个字符的所有索引sub，然后过滤掉与 where不是从该索引开始的前缀str不对齐的索引。sub这解决了查找所有索引的问题。

然后我们可以简单地利用这个功能indexOfSubStr。我可以把函数写成

indexOfSubStr sub str = listToMaybe $ indicesOfSubStr sub str

事实上，这样缩短了整整 8 个字符，但我通常已经(.:)定义了运算符，谁不喜欢无点？如果您对它的作用感到困惑（定义有点神秘，类型签名也是如此），它本质上只是由一个带有两个参数函数的单个参数函数组成。

于 2013-11-02T18:54:14.013 回答