子串索引

Question

我对F＃很新。我写了一个函数，它返回目标中子串匹配索引的数组，并且它与我在C＃中编写的类似。

是否有解决此问题的更实用的方法，并且可以在不使用任何可变变量的情况下解决该问题？

let SubStringIndices (haystack:string) (needle:string) = 
    let mutable indices = System.Collections.Generic.List<int>() 
    let mutable index = haystack.IndexOf(needle) 
    while index >= 0 do 
     indices.Add(index) 
     index <- haystack.IndexOf(needle, index+1) 
    indices.ToArray() 

printfn "%A" (SubStringIndices "abaabababaaab" "ab") 
// prints [|0; 3; 5; 7; 11|] 

我不想找一个解决方案，检查每个索引的子串匹配。

Answer 1

像

let SubStringIndices (haystack:string) (needle:string) = 
    -1 |> Seq.unfold (fun n -> 
     let idx = haystack.IndexOf(needle, n + 1) 
     if idx <> -1 then Some(idx, idx) else None   
     ) 

Answer 2

下面是一个简单的递归函数，做同样的事情：

let rec subStringIndices (haystack:string) (needle:string) (from:int) = 
    let index = haystack.IndexOf(needle, from) 
    if index >= 0 then 
    let rest = subStringIndices haystack needle (index + 1) 
    index::rest 
    else [] 

printfn "%A" (subStringIndices "abaabababaaab" "ab" 0) 

的函数使用表示开始索引（要启动字符串搜索）的附加参数from。最初，这被设置为零。在函数中，我们首先得到下一个索引。如果我们找到了某些东西，我们递归地处理字符串的其余部分（从index + 1开始），并返回一个包含索引和所有递归获取索引的列表。

使用尾递归可以使用累加器参数特技和嵌套函数被写入稍微更优雅和更高效的版本：

let subStringIndices (haystack:string) (needle:string) = 
    let rec loop (from:int) acc = 
    let index = haystack.IndexOf(needle, from) 
    if index >= 0 then 
     loop (index + 1) (index::acc) 
    else 
     List.rev acc 
    loop 0 [] 

递归循环现在由loop功能实现。它从外部获取haystack和needle作为参数，所以这些不需要复制到堆栈上。我们累积acc列表中的索引作为参数传递，当我们到达最后时，我们返回列表（反转，因为我们向前面添加了新项目）。