This is grappe. 

grappe is a program for fast searching a text file for regular
expressions (patterns) of the following form:
	w11#...#w1m|w21#...|...|wn1#...#wnl
Here wij's are strings (called fragments), `|' is the union (`OR')
operator, and # is a symbol matching any string (equivalent to .* in
egrep, or to * in UNIX shell). # is called "(arbitrary) wild card" or
"(variable-length) don't care symbol". For example, doc#comp|sos#var
matches any text containing an occurrence of "doc" followed, within
arbitrary distance, by an occurrence of "comp", or alternatively a
text containing an occurrence of "sos" followed by an occurrence of
"var".

grappe implements an algorithm described in

	G.Kucherov, M.Rusinowitch,
	Matching a Set of Strings with Variable Length Don't Cares,
	6th Symposium  on  Combinatorial Pattern Matching, 
	Helsinki, July 1995, Lecture Notes in Computer Science, 
	vol. 937, (1995), pp 230-247. 
	Extended version is to appear in Theoretical Computer Science

The paper is also available at 
http://www.loria.fr/~kucherov/PAPERS/KuchRusiCPM95.ps

Roughly speaking, the speed of grappe is gained by searching for all
alternatives simultaneously rather than treating them separately. This
is achieved by using the DAWG (Directed Acyclic Word Graph) data
structure. 

In contrast to other search tools (egrep, agrep), grappe supports BIG
patterns. Currently, patterns are unions of up to 10 subexpressions,
each containing up to 10 fragmens, and each fragment is of length at
most 256. However, these limitations are arbitrary and can be lifted. 

Another feature is that grappe is not record oriented. grappe
considers the whole text file as a single record. Thus, grappe is
good in searching BIG patterns in LONG texts.

To compile, run make in the grappe directory after untar'ing the tar
file (tar -xf grappe.tar). 

The tar file contains the C source code (files match.c ehren.c
defs.h), Makefile, and this README file.

To call grappe, type either
	grappe pattern-string text-file
(if pattern is short and can be specified explicitely), or
	grappe -f pattern-file text-file
(if pattern is stored in pattern-file)

For example, 
	grappe 'doc#comp|sos#var' textfile
searches textfile for the pattern doc#comp|sos#var (attn: spaces
are meaningful!);
	grappe patfile textfile
searches textfile for the pattern contained in patfile.

Important: grappe has been designed for experimental purposes, and
there remains A LOT of room for optimization. The author would be
grateful for communicating to him a "declaration of interest" in using
grappe, and is ready to contribute to customizing grappe to a specific
usage. 

Author: Gregory Kucherov, INRIA-Lorraine/CRIN, BP 101, 54602
Villers-les-Nancy, France. kucherov@loria.fr
Any reports/suggestions/comments/critics/... are welcome.

Other contributors: Michael Rusinowitch, Paul Zimmermann