子串索引

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列表中的索引作爲參數傳遞，當我們到達最後時，我們返回列表（反轉，因爲我們向前面添加了新項目）。