Amazing result hand made search with F#

General
1

I am reading Algoritms Nikolas Wirt and re-write find substring by example from book

    module Text =

        /// поиск индекс первого вхождения образца в строке
        let findFirst (s: string) (p: string) =
            // предикат проверяющий совпадение части строки с образцом
            let eqSample i (s: string) (p: string) =
                let rec loop j =
                    if j < p.Length && p.[j] = s.[i + j] then
                        loop (j + 1)
                    else
                        j
                loop 0

            let rec loop i =
                if i <= s.Length - p.Length then
                    let dx = eqSample i s p
                    if dx = p.Length then i // нашли подстроку
                    else loop (i + dx + 1)
                else -1 // Возвращаем -1, если не найдено
            
            if p.Length > s.Length || p.Length = 0 
            then -1
            else loop 0

> content.IndexOf substring;;
Real: 00:00:00.023, CPU: 00:00:00.023, GC gen0: 0, gen1: 0, gen2: 0
val it: int = 468658

> Text.findFirst content substring;;
Real: 00:00:00.003, CPU: 00:00:00.003, GC gen0: 0, gen1: 0, gen2: 0
val it: int = 468658

It is fine!

3

Hello,
you’ve successfully implemented and tested the findFirst function for finding the first occurrence of a substring in a string using a custom algorithm. The implementation is working as expected and performs quite efficiently, as you’ve observed that the execution time for your version is faster than using content.IndexOf.

The core logic you’ve used to search for the substring seems to break down the problem well, with the helper function eqSample checking for character-by-character equality readworks.oge and your loop function iterating through the string to find a match.

Best Regard,
Frank