The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Fire-Engine and Spare-Parts String and Language Algorithms

Fire Engine and Spare Parts -- Regular Language Algorithms

FIRE Engine is a finite automata toolkit, written in C++ by Bruce Watson. It provides production quality implementations of finite automata and regular expression algorithms, specifically the construction of finite Several finite automata minimization algorithms have been implemented, including Hopcroft's O(n lg n) algorithm. Both deterministic and non-deterministic automata are supported, and it has been used for compiler construction, hardware modeling, and computational biology applications. It is strictly a computing engine, and does not provide a graphical user-interface.

SPARE Parts is a string pattern recognition toolkit, written in C++ by Bruce Watson. It provides production quality implementations of all major variants of the classical string matching algorithms for single patterns (both Knuth-Morris-Pratt and Boyer-Moore) and multiple patterns (both Aho-Corasick and Commentz-Walter).

Greatly improved commercial versions of both codes are available from, with older versions available from and available by anonymous FTP from in the directory /pub/techreports/pi/ Neither version in the public domain, and neither is copy-left. They are both freely available for noncommercial use (research, experimentation, etc., but not even shareware). They must not be redistributed, but people can simply tell their friends where to get their own copy.

  • Download Files (local site)
  • FASTAR (Finite Automata Systems --- Theoretical and Applied Research) Homepage
  • Bruce Watson’s Webpage

    Problem Links

    Finite State Machine Minimization (8)
    String Matching (8)

    This page last modified on 2008-07-10 .