cl-string-match
CL-STRING-MATCH provides substring (subsequence) search and text processing algorithms implementations including regular expression, prefix/suffix tree data structures, etc.

This library implements such algorithms as:

  • Brute-force (also known as na├»ve algorithm)
  • Boyer-Moore
  • Rabin-Karp
  • Knuth-Morris-Pratt
and others.

It also offers a portable version of the RE regular expression engine developed by Jeffrey Massung. The RE engine is a small, lightweight, and quick, regular expression library. It is a non-recursive, backtracking VM. The syntax is similar to Lua-style pattern matching, but has added support for additional regex features (e.g. a|b, (?..), etc). It's certainly not the fastest, but is easy to understand and extend.

The project has a Wiki that provides information about the string matching in general and a survey of regular expression engines implementation in Common Lisp in particular.

See also