KMPautomaton
functor
signature KMP
functor KMPautomaton
(LABEL) : KMP
A functor constructing a Knuth-Morris-Pratt search automaton to search for single pattern strings in a text.
type t
datatype
s
= Dummy| Pat of t
structure M : PPCFM
val kmp : t list -> s M.machine
val display : t list -> OS.Process.status
val find : t list -> t list -> int list
type t
datatype
s
= Dummy| Pat of t
kmp pat
display pat
find pat txt
ppMatcher
Using the dummy symbols, the restriction on the alphabet of simpleKMPautomaton is avoided: the search continues beyond the first letter of the text that is not in the pattern:
Example:Note that the KMP-automaton for pat is just the minimal deterministic automaton for Alphabet*;pat. Therefore, the functor ppMatcher is more general than KMPautomaton. But note that ppMatcher reports hits by their end positions, so it can report hits for several patterns simultaneously.
- structure IntKmp = KMPautomaton(IntLabels); structure IntKmp : KMP? - IntKmp.find [0,0] [0,0,0,1,0,1,0,0,0,1,0]; val it = [0,1,6,7] : int list