Indizes der Teilzeichenkette

Question

Ich bin sehr neu in F#. Ich schrieb eine Funktion, die ein Array der Indizes der Teilzeichenfolge Übereinstimmungen im Ziel zurückgibt und seine ähnlich wie ich in C# schreiben.

Gibt es einen funktionelleren Weg, dieses Problem zu lösen, und kann es ohne die Verwendung veränderlicher Variablen gelöst werden?

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|]

Ich bin nicht auf der Suche nach einer Lösung, die bei jedem Index auf Teilstringübereinstimmung prüft.

Answer 1

Etwas wie

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

Hier ist eine einfache rekursive Funktion, die das Gleiche tut:

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)

Die Funktion benötigt einen zusätzlichen Parameter from der den Startindex darstellt (wo Sie mit der Suche in der Zeichenkette beginnen wollen). Anfänglich ist dieser Wert auf Null gesetzt. In der Funktion erhalten wir zunächst den nächsten Index. Wenn wir etwas finden, verarbeiten wir rekursiv den Rest der Zeichenkette (beginnend bei index + 1 ) und geben eine Liste zurück, die den Index und alle rekursiv erhaltenen Indizes enthält.

Eine etwas elegantere und effizientere Version, die die Heckrekursion kann unter Verwendung der Akkumulationsparameter Trick und verschachtelte Funktion:

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 []

Die rekursive Schleifenbildung wird nun durch die loop Funktion. Sie erhält haystack y needle als Parameter von außen, so dass diese nicht auf den Stack kopiert werden müssen. Wir akkumulieren die Indizes in der acc Liste als Parameter übergeben, und wenn wir das Ende erreicht haben, geben wir die Liste zurück (umgekehrt, weil wir neue Elemente nach vorne hinzugefügt haben).