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

Я очень новичок в 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|]

Я не ищу решение, которое проверяет соответствие подстроки по каждому индексу.


f# substring
person Rozuur    schedule 02.03.2011    source источник
comment
Кстати, в этом примере нет необходимости делать indices изменяемым. Этот тип коллекции является изменяемым сам по себе. Объявляя indices mutable, вы создаете изменяемую ссылку на изменяемую коллекцию.   -  person wmeyer    schedule 02.03.2011

Ответы (2)


arrow_upward
5
arrow_downward

что-то типа

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        
        )
person desco    schedule 02.03.2011
comment
это должно быть Some (idx, idx) .. unfold - это то, что я искал, спасибо - person Rozuur; 02.03.2011
comment
Спасибо, сделал опечатку при вводе прямо в браузере - person desco; 02.03.2011

arrow_upward
4
arrow_downward

Вот простая рекурсивная функция, которая делает то же самое:

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

person Tomas Petricek    schedule 02.03.2011
comment
но это не может быть функциональным, вы не использовали совпадение ... с любым местом! ;) - person Massif; 02.03.2011
comment
@Massif :-) рекурсия должна быть достаточно хорошей! Но вы можете использовать match для тестирования index (это не сделает код лучше, поэтому я этого не делал) - person Tomas Petricek; 02.03.2011