| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 |
- Bm is a fast pattern matching utility, intended to be almost
- identical in functionality to fgrep (ugh!) but much faster. It uses
- the Boyer-Moore algorithm, as described in the papers listed below:
- D.E. Knuth, J.H. Morris, V.R. Pratt,"Fast Pattern Matching in Strings",
- SIAM J. Comput., 6(2), June 1977, 323-350,
- Z. Galil,
- "On Improving the Worst Case Running Time of the Boyer-Moore String
- Matching Algorithm",
- CACM, 22(9), Sept. 1979, ACM,
- R.S. Boyer, J.S. Moore,"A Fast String Searching Algorithm", CACM, 20(10),
- Oct. 1977, 762-772,
- G. de V. Smit,"A Comparison of Three String Matching Algorithms",
- Software - Practice and Experience, vol. 12, 1982, 57-66,
- *** NOTE *** There are certain system dependencies in the code.
- Please check whether your system uses "index" or "strchr" to
- find a character in a string: this affects MkDescVec.c.
- Also check whether your system uses <strings.h> or <string.h>.
- This affects match.c/bm.c, MkDescVec.c, and PrintLine.c.
- Also check whether your system has "bcopy". If so, see MoveResidue.c
- The files are MkDescVec.c, PrintLine.c, bm.c, and
- Execute.c: search a file for the patterns
- Extern.h: declarations of externs
- GetPatFile.c: read in patterns from a file and set up a vector of
- pattern descriptors
- Global.c: global variables (complement to Extern.h)
- MakeDesc.c: create a pattern descriptor for one pattern, including
- skip tables, etc.
- MakeSkip.c: make the skip tables for one pattern
- Makefile: you can figure this one out for yourself
- MatchFound.c: what to do when you actually FIND a pattern - print it,
- update flags, etc.
- MkDescVec.c: make a vector of pattern descriptors, given a string
- of newline-separated patterns
- MoveResidue.c: when you come to the end of the buffer, move the
- unsearched "residue" to the beginning and start again
- PrintLine.c: print the appropriate stuff after finding a match
- PutUsage.c: mini-man page.
- README: this file
- Search.c: the guts. Implements B-M algorithm given a pattern, skip
- tables for the pattern, and a buffer to search
- bm.c: mainline. mostly interpreting the command line and tidying
- up at the end. Calls Execute for each file.
- bm.h: constants
- bm.p: man page
|
