The simpleKMPautomaton functor

Synopsis

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


Description

type t


the type of letters taken from the input structure.

display pat

displays the automaton for searching with pattern pat. Writes files kmp.tmp.dot and kmp.tmp.ps.

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.

Discussion

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.

Example:

- 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