Индексы подстроки

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, переданном в качестве параметра, и когда мы достигаем конца, мы возвращаем список (в обратном порядке, потому что мы добавляли новые элементы в начало списка).