25.19 Rabin–Karp string search

The library (vicare containers strings rabin-karp) implements the Rabin–Karp string search algorithm.

Opaque Object Type: rabin-karp

Scheme object type, disjoint from all the other types, holding the state for repeated string searches using the same pattern over different texts.

Function: make-rabin-karp pattern

Function: make-rabin-karp pattern base

Function: make-rabin-karp pattern base prime

Build and return a new rabin-karp object. pattern must be a Scheme string representing the pattern to search for. base must be a fixnum used in the rolling hash algorithm (when in doubt use 256); it defaults to 256. prime must be a “large” prime fixnum (when in doubt use 472882049); it defaults to 472882049.

Function: rabin-karp? obj

Return #t if obj is a rabin-karp object, otherwise return #f.

Validation Clause: rabin-karp obj

Validation clause to be used with the facilities of the library (vicare arguments validation). Succeed if obj satisfies the predicate rabin-karp?.

Function: rabin-karp-search rabin-karp text

Perform the search of a pattern over text, which must be a Scheme string. If successful: return the offset of the first character of the first occurrence of pattern in text; else return #f.

Examples:

#!r6rs
(import (vicare)
  (vicare containers strings rabin-karp))

(define S (make-rabin-karp "ciao"))
(rabin-karp-search S "012345ciao")      ⇒ 6
(rabin-karp-search S "hello world")     ⇒ #f