An efficient implementation of static string pattern matching machines

A technique for implementing a static transition table of a string pattern matching machine which locates all occurrences of a finite number of keywords in a string is described. The approach is based on S.C. Johnson's (1975) storage and retrieval method of the transition table of a finite-state machine. By restricting the transition table of the finite-state machine to that of the string pattern-matching machine, triple arrays of Johnsons's data structure can be reduced to two arrays. The retrieval program of the reduced data structure can be speeded up by a finite straight program without loops.>