Module Aho_corasick

Aho–Corasick multi-pattern string matching.

Build an automaton from a set of patterns once, then find every occurrence of every pattern in an input with a single left-to-right pass. Search takes O(input length + matches examined); overlapping searches also allocate their reported matches.

Matching is byte-oriented and 8-bit clean: patterns and inputs are arbitrary strings (UTF-8 works as byte matching; ?ignore_case folds ASCII letters only).

Reference: Aho & Corasick, "Efficient string matching: an aid to bibliographic search", CACM 18(6), 1975.

type t

A compiled automaton. Immutable and safe to share across threads.

type match_ = {
  1. pattern : int;
    (*

    Index of the pattern in the list given to build.

    *)
  2. start : int;
    (*

    Byte offset of the first matched byte.

    *)
  3. stop : int;
    (*

    Byte offset one past the last matched byte.

    *)
}
val build : ?ignore_case:bool -> string list -> t

build patterns compiles the automaton. Duplicate patterns are allowed (each occurrence reports every duplicate's index). With ~ignore_case:true, ASCII letters match case-insensitively. An empty pattern list yields an automaton that matches nothing.

Raises Invalid_argument if any pattern is the empty string.

val pattern_count : t -> int

Number of patterns, including duplicates.

val pattern : t -> int -> string

The original pattern for a match_'s pattern index.

Raises Invalid_argument if the index is out of bounds.

Searching

val find_all : t -> string -> match_ list

Every match of every pattern, including overlapping ones. Ordered by stop; matches ending at the same position come longest first, then by ascending pattern index for equal lengths.

val find_iter : t -> string -> match_ Stdlib.Seq.t

Like find_all, but lazily — stop consuming to stop scanning.

val find_leftmost_longest : t -> string -> match_ list

Non-overlapping matches, chosen greedily: repeatedly take the match with the smallest start (breaking ties by greatest length), then discard everything overlapping it. Equal-length ties use the lowest pattern index. Selection is a single pass and retains at most one candidate per start within the longest-pattern window.

val mem : t -> string -> bool

Does any pattern occur? Scans only as far as the first match.

val replace_all : t -> f:(match_ -> string) -> string -> string

Replace each find_leftmost_longest match m with f m.

module Stream : sig ... end