The simpleKMPautomaton functor


signature simpleKMP
functor simpleKMPautomaton (LABEL) : simpleKMP

A functor constructing a Knuth-Morris-Pratt search automaton to search for single pattern strings in a text.

Functor result interface

structure M : PPCFM
type t
val display : t list -> OS.Process.status
val kmp : t list -> t M.machine
val find : t list -> t list -> int list


type t
the type of letters taken from the input structure.

display pat
displays the automaton for searching with pattern pat. Writes files and

kmp pat
returns the automaton that searches its input for occurrences of pat.

find pat txt
returns the list of initial positions of occurrences of pat in txt.


Since our automata assume that the alphabet consists of the letters occurring in the transitions, no letters except those in the input string may appear in the search text.

- structure IntKmp = simpleKMPautomaton(IntLabels);
structure IntKmp : simpleKMP?

- IntKmp.find [0,0,1] [0,0,0,1,0,1,0,0,0,1,0];
val it = [1,7] : int list
However, by the restriction on the alphabet the search stops at the first letter of the text that is not in the pattern:
- IntKmp.find [0,0] [0,0,0,1,0,1,0,0,0,1,0];
val it = [0,1] : int list
For the general case without this restriction, see KMPautomaton. For multiple pattern search, see ppMatcher.