home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: SHell self-extracting ARchive
(archive/shar).
You can browse this item here: egrep
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Newsgroup Content (archive/news)
| magic
| Supported |
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| news or mail, ASCII text
| default
| |
| 100%
| TrID
| E-Mail message (Var. 2)
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| message/rfc822
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 3a 20 4a 61 | 6d 65 73 20 41 2e 20 57 |From: Ja|mes A. W|
|00000010| 6f 6f 64 73 20 3c 67 65 | 6e 72 61 64 21 64 65 63 |oods <ge|nrad!dec|
|00000020| 76 61 78 21 64 65 63 77 | 72 6c 21 6a 61 77 40 52 |vax!decw|rl!jaw@R|
|00000030| 49 41 43 53 2e 41 52 50 | 41 3e 0a 53 75 62 6a 65 |IACS.ARP|A>.Subje|
|00000040| 63 74 3a 20 65 67 72 65 | 70 20 2d 20 4d 6f 72 65 |ct: egre|p - More|
|00000050| 20 50 65 70 20 66 6f 72 | 20 42 6f 79 65 72 2d 4d | Pep for| Boyer-M|
|00000060| 6f 6f 72 65 20 47 72 65 | 70 0a 4e 65 77 73 67 72 |oore Gre|p.Newsgr|
|00000070| 6f 75 70 73 3a 20 6d 6f | 64 2e 73 6f 75 72 63 65 |oups: mo|d.source|
|00000080| 73 0a 41 70 70 72 6f 76 | 65 64 3a 20 6a 70 6e 40 |s.Approv|ed: jpn@|
|00000090| 70 61 6e 64 61 2e 55 55 | 43 50 0a 0a 4d 6f 64 2e |panda.UU|CP..Mod.|
|000000a0| 73 6f 75 72 63 65 73 3a | 20 20 56 6f 6c 75 6d 65 |sources:| Volume|
|000000b0| 20 34 2c 20 49 73 73 75 | 65 20 34 37 0a 53 75 62 | 4, Issu|e 47.Sub|
|000000c0| 6d 69 74 74 65 64 20 62 | 79 3a 20 4a 61 6d 65 73 |mitted b|y: James|
|000000d0| 20 41 2e 20 57 6f 6f 64 | 73 20 3c 61 6d 65 73 21 | A. Wood|s <ames!|
|000000e0| 6a 61 77 40 52 49 41 43 | 53 2e 41 52 50 41 3e 0a |jaw@RIAC|S.ARPA>.|
|000000f0| 0a 0a 61 73 20 61 64 76 | 65 72 74 69 73 65 64 20 |..as adv|ertised |
|00000100| 69 6e 20 6e 65 74 2e 75 | 6e 69 78 2e 20 20 2d 2d |in net.u|nix. --|
|00000110| 20 61 6d 65 73 21 6a 61 | 77 0a 0a 2d 2d 2d 2d 2d | ames!ja|w..-----|
|00000120| 2d 2d 2d 2d 2d 0a 23 21 | 20 2f 62 69 6e 2f 73 68 |-----.#!| /bin/sh|
|00000130| 0a 23 20 54 68 69 73 20 | 69 73 20 61 20 73 68 65 |.# This |is a she|
|00000140| 6c 6c 20 61 72 63 68 69 | 76 65 2c 20 6d 65 61 6e |ll archi|ve, mean|
|00000150| 69 6e 67 3a 0a 23 20 31 | 2e 20 52 65 6d 6f 76 65 |ing:.# 1|. Remove|
|00000160| 20 65 76 65 72 79 74 68 | 69 6e 67 20 61 62 6f 76 | everyth|ing abov|
|00000170| 65 20 74 68 65 20 23 21 | 20 2f 62 69 6e 2f 73 68 |e the #!| /bin/sh|
|00000180| 20 6c 69 6e 65 2e 0a 23 | 20 32 2e 20 53 61 76 65 | line..#| 2. Save|
|00000190| 20 74 68 65 20 72 65 73 | 75 6c 74 69 6e 67 20 74 | the res|ulting t|
|000001a0| 65 78 74 20 69 6e 20 61 | 20 66 69 6c 65 2e 0a 23 |ext in a| file..#|
|000001b0| 20 33 2e 20 45 78 65 63 | 75 74 65 20 74 68 65 20 | 3. Exec|ute the |
|000001c0| 66 69 6c 65 20 77 69 74 | 68 20 2f 62 69 6e 2f 73 |file wit|h /bin/s|
|000001d0| 68 20 28 6e 6f 74 20 63 | 73 68 29 20 74 6f 20 63 |h (not c|sh) to c|
|000001e0| 72 65 61 74 65 20 74 68 | 65 20 66 69 6c 65 73 3a |reate th|e files:|
|000001f0| 0a 23 09 70 65 70 34 67 | 72 65 70 2e 31 0a 23 09 |.#.pep4g|rep.1.#.|
|00000200| 70 65 70 34 67 72 65 70 | 2e 32 0a 23 09 4d 61 6b |pep4grep|.2.#.Mak|
|00000210| 65 66 69 6c 65 0a 23 09 | 65 67 72 65 70 2e 63 0a |efile.#.|egrep.c.|
|00000220| 23 09 63 6f 6d 70 61 74 | 2d 73 79 73 35 2e 63 0a |#.compat|-sys5.c.|
|00000230| 23 20 54 68 69 73 20 61 | 72 63 68 69 76 65 20 63 |# This a|rchive c|
|00000240| 72 65 61 74 65 64 3a 20 | 57 65 64 20 41 70 72 20 |reated: |Wed Apr |
|00000250| 20 32 20 31 38 3a 31 39 | 3a 31 34 20 31 39 38 36 | 2 18:19|:14 1986|
|00000260| 0a 65 78 70 6f 72 74 20 | 50 41 54 48 3b 20 50 41 |.export |PATH; PA|
|00000270| 54 48 3d 2f 62 69 6e 3a | 24 50 41 54 48 0a 65 63 |TH=/bin:|$PATH.ec|
|00000280| 68 6f 20 73 68 61 72 3a | 20 65 78 74 72 61 63 74 |ho shar:| extract|
|00000290| 69 6e 67 20 22 27 70 65 | 70 34 67 72 65 70 2e 31 |ing "'pe|p4grep.1|
|000002a0| 27 22 20 27 28 36 31 30 | 34 20 63 68 61 72 61 63 |'" '(610|4 charac|
|000002b0| 74 65 72 73 29 27 0a 69 | 66 20 74 65 73 74 20 2d |ters)'.i|f test -|
|000002c0| 66 20 27 70 65 70 34 67 | 72 65 70 2e 31 27 0a 74 |f 'pep4g|rep.1'.t|
|000002d0| 68 65 6e 0a 09 65 63 68 | 6f 20 73 68 61 72 3a 20 |hen..ech|o shar: |
|000002e0| 77 69 6c 6c 20 6e 6f 74 | 20 6f 76 65 72 2d 77 72 |will not| over-wr|
|000002f0| 69 74 65 20 65 78 69 73 | 74 69 6e 67 20 66 69 6c |ite exis|ting fil|
|00000300| 65 20 22 27 70 65 70 34 | 67 72 65 70 2e 31 27 22 |e "'pep4|grep.1'"|
|00000310| 0a 65 6c 73 65 0a 63 61 | 74 20 3c 3c 20 5c 53 48 |.else.ca|t << \SH|
|00000320| 41 52 5f 45 4f 46 20 3e | 20 27 70 65 70 34 67 72 |AR_EOF >| 'pep4gr|
|00000330| 65 70 2e 31 27 0a 3e 46 | 72 6f 6d 20 70 6f 73 74 |ep.1'.>F|rom post|
|00000340| 6e 65 77 73 20 54 75 65 | 20 4d 61 72 20 31 38 20 |news Tue| Mar 18 |
|00000350| 31 38 3a 30 34 3a 30 38 | 20 31 39 38 36 0a 53 75 |18:04:08| 1986.Su|
|00000360| 62 6a 65 63 74 3a 20 4d | 6f 72 65 20 50 65 70 20 |bject: M|ore Pep |
|00000370| 66 6f 72 20 42 6f 79 65 | 72 2d 4d 6f 6f 72 65 20 |for Boye|r-Moore |
|00000380| 47 72 65 70 20 28 70 61 | 72 74 20 31 20 6f 66 20 |Grep (pa|rt 1 of |
|00000390| 32 29 0a 4e 65 77 73 67 | 72 6f 75 70 73 3a 20 6e |2).Newsg|roups: n|
|000003a0| 65 74 2e 75 6e 69 78 0a | 0a 23 20 20 54 68 65 20 |et.unix.|.# The |
|000003b0| 63 68 69 65 66 20 64 65 | 66 65 63 74 20 6f 66 20 |chief de|fect of |
|000003c0| 48 65 6e 72 79 20 4b 69 | 6e 67 0a 20 20 20 57 61 |Henry Ki|ng. Wa|
|000003d0| 73 20 63 68 65 77 69 6e | 67 20 6c 69 74 74 6c 65 |s chewin|g little|
|000003e0| 20 62 69 74 73 20 6f 66 | 20 73 74 72 69 6e 67 2e | bits of| string.|
|000003f0| 0a 0a 09 2d 2d 20 48 69 | 6c 61 69 72 65 20 42 65 |...-- Hi|laire Be|
|00000400| 6c 6c 6f 63 2c 20 43 61 | 75 74 69 6f 6e 61 72 79 |lloc, Ca|utionary|
|00000410| 20 54 61 6c 65 73 20 5b | 31 39 30 37 5d 0a 0a 23 | Tales [|1907]..#|
|00000420| 20 20 41 74 74 65 6d 70 | 74 20 74 68 65 20 65 6e | Attemp|t the en|
|00000430| 64 2c 20 61 6e 64 20 6e | 65 76 65 72 20 73 74 61 |d, and n|ever sta|
|00000440| 6e 64 20 74 6f 20 64 6f | 75 62 74 0a 20 20 20 4e |nd to do|ubt. N|
|00000450| 6f 74 68 69 6e 67 27 73 | 20 73 6f 20 68 61 72 64 |othing's| so hard|
|00000460| 20 62 75 74 20 73 65 61 | 72 63 68 20 77 69 6c 6c | but sea|rch will|
|00000470| 20 66 69 6e 64 20 69 74 | 20 6f 75 74 2e 0a 0a 09 | find it| out....|
|00000480| 2d 2d 20 52 6f 62 65 72 | 74 20 48 65 72 72 69 63 |-- Rober|t Herric|
|00000490| 6b 2c 20 48 65 73 70 65 | 72 69 64 65 73 20 5b 31 |k, Hespe|rides [1|
|000004a0| 36 34 38 5d 0a 0a 20 20 | 20 20 20 54 68 65 20 77 |648].. | The w|
|000004b0| 6f 72 6c 64 20 64 6f 65 | 73 20 6e 6f 74 20 6e 65 |orld doe|s not ne|
|000004c0| 65 64 20 61 6e 6f 74 68 | 65 72 20 27 67 72 65 70 |ed anoth|er 'grep|
|000004d0| 27 20 76 61 72 69 61 6e | 74 2e 20 20 41 6e 64 20 |' varian|t. And |
|000004e0| 73 6f 2c 20 77 68 61 74 | 20 69 73 20 74 68 69 73 |so, what| is this|
|000004f0| 0a 77 65 20 6f 66 66 65 | 72 3f 20 20 4f 6e 20 74 |.we offe|r? On t|
|00000500| 68 65 20 73 75 72 66 61 | 63 65 2c 20 74 68 65 20 |he surfa|ce, the |
|00000510| 65 78 61 63 74 20 73 61 | 6d 65 20 27 65 67 72 65 |exact sa|me 'egre|
|00000520| 70 27 20 61 63 74 75 61 | 6c 6c 79 2c 20 62 75 74 |p' actua|lly, but|
|00000530| 20 75 6e 64 65 72 6e 65 | 61 74 68 2c 0a 61 20 73 | underne|ath,.a s|
|00000540| 77 69 66 74 20 42 6f 79 | 65 72 2d 4d 6f 6f 72 65 |wift Boy|er-Moore|
|00000550| 20 68 79 62 72 69 64 2c | 20 69 6e 20 43 2c 20 77 | hybrid,| in C, w|
|00000560| 68 69 63 68 20 63 61 6e | 20 62 65 61 74 20 61 73 |hich can| beat as|
|00000570| 73 65 6d 62 6c 65 72 20 | 76 65 72 73 69 6f 6e 73 |sembler |versions|
|00000580| 20 75 74 69 6c 69 7a 69 | 6e 67 0a 6d 69 63 72 6f | utilizi|ng.micro|
|00000590| 63 6f 64 65 64 20 73 74 | 72 69 6e 67 20 73 65 61 |coded st|ring sea|
|000005a0| 72 63 68 20 69 6e 73 74 | 72 75 63 74 69 6f 6e 73 |rch inst|ructions|
|000005b0| 2e 20 20 54 68 65 20 6f | 66 66 65 72 69 6e 67 2c |. The o|ffering,|
|000005c0| 20 64 65 73 69 67 6e 65 | 64 20 69 6e 20 74 68 65 | designe|d in the|
|000005d0| 0a 4b 65 72 6e 69 67 68 | 61 6e 69 61 6e 20 73 65 |.Kernigh|anian se|
|000005e0| 6e 73 65 20 74 6f 20 75 | 74 69 6c 69 7a 65 20 74 |nse to u|tilize t|
|000005f0| 68 65 20 65 78 69 73 74 | 69 6e 67 20 27 65 67 72 |he exist|ing 'egr|
|00000600| 65 70 27 20 77 68 65 6e | 20 69 74 20 6d 75 73 74 |ep' when| it must|
|00000610| 2c 20 61 6c 73 6f 0a 6d | 61 6b 65 73 20 75 73 65 |, also.m|akes use|
|00000620| 20 6f 66 20 4d 72 2e 20 | 48 65 6e 72 79 20 53 70 | of Mr. |Henry Sp|
|00000630| 65 6e 63 65 72 27 73 20 | 72 65 67 65 78 70 28 33 |encer's |regexp(3|
|00000640| 29 20 66 75 6e 63 74 69 | 6f 6e 73 20 69 6e 20 61 |) functi|ons in a|
|00000650| 6e 20 75 6e 75 73 75 61 | 6c 20 77 61 79 2e 0a 46 |n unusua|l way..F|
|00000660| 6f 72 20 74 68 65 20 65 | 64 69 66 69 63 61 74 69 |or the e|dificati|
|00000670| 6f 6e 20 6f 66 20 74 68 | 6f 73 65 20 77 69 74 68 |on of th|ose with|
|00000680| 6f 75 74 20 6f 6e 2d 6c | 69 6e 65 20 61 63 63 65 |out on-l|ine acce|
|00000690| 73 73 20 74 6f 20 73 79 | 73 74 65 6d 20 73 6f 75 |ss to sy|stem sou|
|000006a0| 72 63 65 20 63 6f 64 65 | 2c 0a 74 68 65 20 76 65 |rce code|,.the ve|
|000006b0| 6e 64 6f 72 2d 73 75 70 | 70 6c 69 65 64 20 27 65 |ndor-sup|plied 'e|
|000006c0| 67 72 65 70 27 20 69 73 | 20 6c 65 66 74 20 69 6e |grep' is| left in|
|000006d0| 20 61 20 70 72 69 73 74 | 69 6e 65 20 73 74 61 74 | a prist|ine stat|
|000006e0| 65 2e 0a 0a 20 20 20 20 | 20 57 69 74 68 20 63 6f |e... | With co|
|000006f0| 64 65 20 6e 6f 77 20 77 | 65 6e 64 69 6e 67 20 69 |de now w|ending i|
|00000700| 74 73 20 77 61 79 20 74 | 6f 20 6d 6f 64 2e 73 6f |ts way t|o mod.so|
|00000710| 75 72 63 65 73 2c 20 77 | 65 20 6f 62 74 61 69 6e |urces, w|e obtain|
|00000720| 20 74 68 65 20 66 6f 6c | 6c 6f 77 69 6e 67 0a 72 | the fol|lowing.r|
|00000730| 65 73 75 6c 74 73 2e 20 | 20 54 69 6d 65 73 20 28 |esults. | Times (|
|00000740| 69 6e 20 73 65 63 6f 6e | 64 73 29 20 61 72 65 20 |in secon|ds) are |
|00000750| 61 6c 6c 20 6d 65 61 73 | 75 72 65 64 20 6f 6e 20 |all meas|ured on |
|00000760| 61 20 56 41 58 20 31 31 | 2f 37 35 30 20 73 79 73 |a VAX 11|/750 sys|
|00000770| 74 65 6d 20 72 75 6e 6e | 69 6e 67 0a 42 53 44 20 |tem runn|ing.BSD |
|00000780| 34 2e 32 20 6f 6e 20 46 | 75 6a 69 74 73 75 20 45 |4.2 on F|ujitsu E|
|00000790| 61 67 6c 65 73 2c 20 61 | 6c 74 68 6f 75 67 68 20 |agles, a|lthough |
|000007a0| 6f 75 72 20 27 65 67 72 | 65 70 27 20 68 61 73 20 |our 'egr|ep' has |
|000007b0| 62 65 65 6e 20 72 75 6e | 20 6f 6e 20 74 68 65 20 |been run| on the |
|000007c0| 53 75 6e 20 32 2c 0a 56 | 37 20 55 6e 69 78 2f 50 |Sun 2,.V|7 Unix/P|
|000007d0| 44 50 20 31 31 2c 20 56 | 61 78 65 6e 20 63 6f 6e |DP 11, V|axen con|
|000007e0| 66 69 67 75 72 65 64 20 | 77 69 74 68 20 53 79 73 |figured |with Sys|
|000007f0| 74 65 6d 20 56 2c 20 61 | 6e 64 2c 20 66 6f 72 20 |tem V, a|nd, for |
|00000800| 61 64 64 65 64 20 65 66 | 66 65 63 74 2c 20 74 68 |added ef|fect, th|
|00000810| 65 0a 4e 41 53 41 20 41 | 6d 65 73 20 43 72 61 79 |e.NASA A|mes Cray|
|00000820| 20 32 2e 0a 0a 09 09 09 | 32 30 30 4b 20 62 79 74 | 2......|200K byt|
|00000830| 65 73 20 20 20 20 20 20 | 20 75 73 65 72 20 20 20 |es | user |
|00000840| 73 79 73 09 6e 6f 74 65 | 73 0a 0a 20 20 28 6e 65 |sys.note|s.. (ne|
|00000850| 77 29 20 65 67 72 65 70 | 20 20 61 73 74 72 69 61 |w) egrep| astria|
|00000860| 6e 20 2f 75 73 72 2f 64 | 69 63 74 2f 77 6f 72 64 |n /usr/d|ict/word|
|00000870| 73 09 20 30 2e 34 20 20 | 20 20 30 2e 35 20 20 20 |s. 0.4 | 0.5 |
|00000880| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|00000890| 62 79 20 22 6a 61 77 22 | 0a 09 6d 61 74 63 68 09 |by "jaw"|..match.|
|000008a0| 20 20 22 20 20 20 20 20 | 20 20 20 20 20 20 22 09 | " | ".|
|000008b0| 09 20 30 2e 35 20 20 20 | 20 30 2e 35 20 20 20 20 |. 0.5 | 0.5 |
|000008c0| 56 41 58 2d 6f 6e 6c 79 | 20 28 57 61 74 65 72 6c |VAX-only| (Waterl|
|000008d0| 6f 6f 29 0a 09 62 6d 09 | 20 20 22 20 20 20 20 20 |oo)..bm.| " |
|000008e0| 20 20 20 20 20 20 22 09 | 09 20 31 2e 31 20 20 20 | ".|. 1.1 |
|000008f0| 20 30 2e 36 20 20 20 20 | 50 65 74 65 72 20 42 61 | 0.6 |Peter Ba|
|00000900| 69 6e 27 73 20 76 65 72 | 73 69 6f 6e 20 32 0a 20 |in's ver|sion 2. |
|00000910| 20 28 6f 6c 64 29 20 65 | 67 72 65 70 20 20 20 20 | (old) e|grep |
|00000920| 20 22 20 20 20 20 20 20 | 20 20 20 20 20 22 20 09 | " | " .|
|00000930| 20 35 2e 36 20 20 20 20 | 31 2e 37 20 20 20 20 73 | 5.6 |1.7 s|
|00000940| 74 61 6e 64 61 72 64 09 | 0a 0a 5b 6e 6f 74 65 3a |tandard.|..[note:|
|00000950| 20 20 74 68 65 20 6f 75 | 74 70 75 74 20 68 65 72 | the ou|tput her|
|00000960| 65 20 69 73 20 74 68 65 | 20 73 69 6e 67 6c 65 20 |e is the| single |
|00000970| 77 6f 72 64 20 22 5a 6f | 72 6f 61 73 74 72 69 61 |word "Zo|roastria|
|00000980| 6e 22 2e 5d 0a 0a 20 20 | 20 20 20 41 68 61 2c 20 |n".].. | Aha, |
|00000990| 79 6f 75 20 71 75 69 70 | 20 2d 2d 20 74 68 69 73 |you quip| -- this|
|000009a0| 20 69 73 20 61 6c 6c 20 | 76 65 72 79 20 66 69 6e | is all |very fin|
|000009b0| 65 20 66 6f 72 20 74 68 | 65 20 39 39 20 61 6e 64 |e for th|e 99 and|
|000009c0| 20 34 34 2f 31 30 30 27 | 73 20 70 65 72 63 65 6e | 44/100'|s percen|
|000009d0| 74 0a 6d 65 74 61 63 68 | 61 72 61 63 74 65 72 2d |t.metach|aracter-|
|000009e0| 66 72 65 65 20 77 6f 72 | 6c 64 2c 20 62 75 74 20 |free wor|ld, but |
|000009f0| 77 68 61 74 20 61 62 6f | 75 74 20 74 69 6d 69 6e |what abo|ut timin|
|00000a00| 67 20 66 6f 72 20 73 68 | 6f 72 74 65 72 20 73 74 |g for sh|orter st|
|00000a10| 72 69 6e 67 73 2c 20 63 | 68 61 72 61 63 74 65 72 |rings, c|haracter|
|00000a20| 0a 66 6f 6c 64 69 6e 67 | 2c 20 61 73 20 77 65 6c |.folding|, as wel|
|00000a30| 6c 20 61 73 20 66 6f 72 | 20 74 68 65 20 6d 6f 72 |l as for| the mor|
|00000a40| 65 20 69 6e 74 65 72 65 | 73 74 69 6e 67 20 75 6e |e intere|sting un|
|00000a50| 69 76 65 72 73 65 20 6f | 66 20 65 78 74 65 6e 64 |iverse o|f extend|
|00000a60| 65 64 20 72 65 67 75 6c | 61 72 20 0a 65 78 70 72 |ed regul|ar .expr|
|00000a70| 65 73 73 69 6f 6e 73 3f | 20 20 53 61 6d 70 6c 65 |essions?| Sample|
|00000a80| 73 20 66 6f 72 74 68 77 | 69 74 68 2e 20 20 28 45 |s forthw|ith. (E|
|00000a90| 67 72 65 70 20 62 65 6c | 6f 77 20 72 65 66 65 72 |grep bel|ow refer|
|00000aa0| 73 20 74 6f 20 74 68 65 | 20 6e 65 77 20 6f 6e 65 |s to the| new one|
|00000ab0| 2c 20 74 69 6d 65 73 20 | 66 6f 72 0a 74 68 65 20 |, times |for.the |
|00000ac0| 2f 75 73 72 2f 62 69 6e | 20 63 6f 64 65 20 62 65 |/usr/bin| code be|
|00000ad0| 69 6e 67 20 61 62 6f 75 | 74 20 74 68 65 20 73 61 |ing abou|t the sa|
|00000ae0| 6d 65 20 61 73 20 61 62 | 6f 76 65 20 6f 6e 20 6d |me as ab|ove on m|
|00000af0| 6f 73 74 20 61 6e 79 20 | 70 61 74 74 65 72 6e 2e |ost any |pattern.|
|00000b00| 29 0a 0a 09 65 67 72 65 | 70 20 09 20 7a 75 72 69 |)...egre|p . zuri|
|00000b10| 63 68 09 09 30 2e 34 20 | 20 30 2e 35 09 30 20 77 |ch..0.4 | 0.5.0 w|
|00000b20| 6f 72 64 73 20 6f 75 74 | 70 75 74 0a 09 65 67 72 |ords out|put..egr|
|00000b30| 65 70 20 2d 69 20 7a 75 | 52 69 63 68 20 20 09 30 |ep -i zu|Rich .0|
|00000b40| 2e 34 20 20 30 2e 35 09 | 31 20 0a 09 65 67 72 65 |.4 0.5.|1 ..egre|
|00000b50| 70 20 2d 69 20 7a 65 75 | 73 20 20 09 09 30 2e 36 |p -i zeu|s ..0.6|
|00000b60| 20 20 30 2e 36 09 31 0a | 09 65 67 72 65 70 20 2d | 0.6.1.|.egrep -|
|00000b70| 69 20 7a 65 6e 20 20 09 | 09 30 2e 37 20 20 30 2e |i zen .|.0.7 0.|
|00000b80| 36 09 31 31 0a 09 62 6d | 20 09 20 7a 65 6e 20 20 |6.11..bm| . zen |
|00000b90| 09 09 32 2e 32 20 20 30 | 2e 36 09 31 30 0a 09 65 |..2.2 0|.6.10..e|
|00000ba0| 67 72 65 70 20 09 20 5a | 5a 20 20 09 09 30 2e 38 |grep . Z|Z ..0.8|
|00000bb0| 20 20 30 2e 36 09 30 0a | 09 62 6d 20 09 20 5a 5a | 0.6.0.|.bm . ZZ|
|00000bc0| 20 20 09 09 33 2e 30 20 | 20 30 2e 37 09 30 0a 09 | ..3.0 | 0.7.0..|
|00000bd0| 65 67 72 65 70 20 2d 63 | 20 5a 20 20 09 09 31 2e |egrep -c| Z ..1.|
|00000be0| 35 20 20 30 2e 36 09 31 | 39 0a 09 62 6d 20 2d 63 |5 0.6.1|9..bm -c|
|00000bf0| 20 09 20 5a 20 20 09 09 | 35 2e 39 20 20 30 2e 37 | . Z ..|5.9 0.7|
|00000c00| 09 31 39 0a 0a 41 64 6d | 69 74 74 65 64 6c 79 2c |.19..Adm|ittedly,|
|00000c10| 20 6d 6f 73 74 20 70 65 | 6f 70 6c 65 20 28 6f 72 | most pe|ople (or|
|00000c20| 20 70 72 6f 67 72 61 6d | 73 29 20 64 6f 6e 27 74 | program|s) don't|
|00000c30| 20 73 65 61 72 63 68 20 | 66 6f 72 20 73 69 6e 67 | search |for sing|
|00000c40| 6c 65 20 63 68 61 72 61 | 63 74 65 72 73 2c 0a 77 |le chara|cters,.w|
|00000c50| 68 65 72 65 20 42 6f 79 | 65 72 2d 4d 6f 6f 72 65 |here Boy|er-Moore|
|00000c60| 20 69 73 20 61 20 62 69 | 74 20 73 6c 6f 77 2c 20 | is a bi|t slow, |
|00000c70| 62 75 74 20 69 74 27 73 | 20 69 6d 70 6f 72 74 61 |but it's| importa|
|00000c80| 6e 74 20 66 6f 72 20 74 | 68 65 20 6c 61 79 65 72 |nt for t|he layer|
|00000c90| 65 64 20 72 65 67 75 6c | 61 72 0a 65 78 70 72 65 |ed regul|ar.expre|
|00000ca0| 73 73 69 6f 6e 20 61 70 | 70 72 6f 61 63 68 20 64 |ssion ap|proach d|
|00000cb0| 65 73 63 72 69 62 65 64 | 20 68 65 72 65 69 6e 2e |escribed| herein.|
|00000cc0| 20 20 57 65 20 6d 69 67 | 68 74 20 70 6f 69 6e 74 | We mig|ht point|
|00000cd0| 20 6f 75 74 20 66 72 6f | 6d 20 74 68 65 20 61 62 | out fro|m the ab|
|00000ce0| 6f 76 65 20 74 68 61 74 | 0a 74 68 65 20 70 6f 70 |ove that|.the pop|
|00000cf0| 75 6c 61 72 20 22 66 6f | 6c 64 22 20 6f 70 74 69 |ular "fo|ld" opti|
|00000d00| 6f 6e 20 63 72 69 70 70 | 6c 65 64 20 62 79 20 27 |on cripp|led by '|
|00000d10| 62 6d 27 20 63 6f 73 74 | 73 20 6c 69 74 74 6c 65 |bm' cost|s little|
|00000d20| 3b 20 69 74 27 73 20 6f | 6e 6c 79 20 61 20 73 6c |; it's o|nly a sl|
|00000d30| 69 67 68 74 0a 61 64 6a | 75 73 74 6d 65 6e 74 20 |ight.adj|ustment |
|00000d40| 6f 66 20 74 68 65 20 70 | 72 65 63 6f 6d 70 75 74 |of the p|recomput|
|00000d50| 65 64 20 22 64 65 6c 74 | 61 22 20 74 61 62 6c 65 |ed "delt|a" table|
|00000d60| 20 61 73 20 77 65 6c 6c | 20 61 73 20 61 20 73 69 | as well| as a si|
|00000d70| 6e 67 6c 65 20 63 68 61 | 72 61 63 74 65 72 0a 61 |ngle cha|racter.a|
|00000d80| 72 72 61 79 20 72 65 66 | 65 72 65 6e 63 65 20 69 |rray ref|erence i|
|00000d90| 6e 20 61 20 73 65 63 6f | 6e 64 61 72 79 20 6c 6f |n a seco|ndary lo|
|00000da0| 6f 70 2e 20 20 57 68 79 | 20 68 61 73 20 42 61 69 |op. Why| has Bai|
|00000db0| 6e 20 63 6c 61 69 6d 65 | 64 20 63 6f 6d 70 6c 65 |n claime|d comple|
|00000dc0| 78 69 74 79 20 66 6f 72 | 20 74 68 69 73 3f 0a 41 |xity for| this?.A|
|00000dd0| 6c 73 6f 2c 20 74 68 65 | 20 74 69 6d 65 73 20 73 |lso, the| times s|
|00000de0| 68 6f 77 20 74 68 61 74 | 20 74 68 65 20 69 6e 6e |how that| the inn|
|00000df0| 65 72 20 6c 6f 6f 70 20 | 63 68 6f 73 65 6e 20 66 |er loop |chosen f|
|00000e00| 6f 72 20 6f 75 72 20 63 | 6f 64 65 20 28 6d 6f 64 |or our c|ode (mod|
|00000e10| 65 6c 65 64 20 61 66 74 | 65 72 0a 74 68 65 20 6f |eled aft|er.the o|
|00000e20| 72 69 67 69 6e 61 6c 20 | 73 70 65 65 64 75 70 20 |riginal |speedup |
|00000e30| 64 6f 6e 65 20 62 79 20 | 42 6f 79 65 72 2d 4d 6f |done by |Boyer-Mo|
|00000e40| 6f 72 65 20 66 6f 72 20 | 74 68 65 20 50 44 50 20 |ore for |the PDP |
|00000e50| 31 30 29 20 63 6f 6e 73 | 69 73 74 65 6e 74 6c 79 |10) cons|istently|
|00000e60| 20 62 65 74 74 65 72 73 | 0a 74 68 65 20 22 62 6c | betters|.the "bl|
|00000e70| 69 6e 64 69 6e 67 6c 79 | 20 66 61 73 74 22 20 76 |indingly| fast" v|
|00000e80| 65 72 73 69 6f 6e 20 62 | 79 20 61 20 66 61 63 74 |ersion b|y a fact|
|00000e90| 6f 72 20 6f 66 20 74 77 | 6f 20 74 6f 20 74 68 72 |or of tw|o to thr|
|00000ea0| 65 65 2e 20 20 54 68 65 | 20 74 69 70 6f 66 66 20 |ee. The| tipoff |
|00000eb0| 77 61 73 0a 66 72 6f 6d | 20 70 72 65 76 69 6f 75 |was.from| previou|
|00000ec0| 73 20 70 61 70 65 72 20 | 73 74 75 64 69 65 73 20 |s paper |studies |
|00000ed0| 28 65 73 70 2e 20 48 6f | 72 73 70 6f 6f 6c 2c 20 |(esp. Ho|rspool, |
|00000ee0| 73 65 65 20 68 65 61 64 | 65 72 20 6e 6f 74 65 73 |see head|er notes|
|00000ef0| 20 69 6e 20 63 6f 64 65 | 29 20 6e 6f 74 69 6e 67 | in code|) noting|
|00000f00| 0a 74 68 61 74 20 74 68 | 65 20 61 6c 67 6f 72 69 |.that th|e algori|
|00000f10| 74 68 6d 20 73 68 6f 75 | 6c 64 2c 20 77 68 65 6e |thm shou|ld, when|
|00000f20| 20 69 6d 70 6c 65 6d 65 | 6e 74 65 64 20 65 66 66 | impleme|nted eff|
|00000f30| 69 63 69 65 6e 74 6c 79 | 2c 20 62 65 73 74 20 74 |iciently|, best t|
|00000f40| 79 70 69 63 61 6c 20 6d | 69 63 72 6f 63 6f 64 65 |ypical m|icrocode|
|00000f50| 2e 0a 4e 6f 77 20 69 74 | 20 64 6f 65 73 2e 20 0a |..Now it| does. .|
|00000f60| 0a 09 77 68 69 6c 65 20 | 28 20 28 6b 20 2b 3d 20 |..while |( (k += |
|00000f70| 64 65 6c 74 61 30 20 28 | 20 2a 6b 20 29 29 20 3c |delta0 (| *k )) <|
|00000f80| 20 73 74 72 65 6e 64 20 | 29 0a 09 09 3b 09 09 2f | strend |)...;../|
|00000f90| 2a 20 6f 76 65 72 20 38 | 30 25 20 6f 66 20 74 69 |* over 8|0% of ti|
|00000fa0| 6d 65 20 73 70 65 6e 74 | 20 68 65 72 65 20 2a 2f |me spent| here */|
|00000fb0| 0a 0a 69 73 20 74 68 65 | 20 6b 65 79 20 28 6d 6f |..is the| key (mo|
|00000fc0| 64 75 6c 6f 20 70 72 65 | 63 6f 6d 70 75 74 61 74 |dulo pre|computat|
|00000fd0| 69 6f 6e 20 74 72 69 63 | 6b 73 29 2c 20 61 6e 64 |ion tric|ks), and|
|00000fe0| 20 74 61 6b 65 73 20 62 | 75 74 20 74 68 72 65 65 | takes b|ut three|
|00000ff0| 20 6f 72 20 66 6f 75 72 | 0a 69 6e 73 74 72 75 63 | or four|.instruc|
|00001000| 74 69 6f 6e 73 20 6f 6e | 20 6d 6f 73 74 20 6d 61 |tions on| most ma|
|00001010| 63 68 69 6e 65 73 2e 0a | 0a 20 20 20 20 20 42 61 |chines..|. Ba|
|00001020| 73 69 63 20 6d 65 74 68 | 6f 64 20 66 6f 72 20 72 |sic meth|od for r|
|00001030| 65 67 75 6c 61 72 20 65 | 78 70 72 65 73 73 69 6f |egular e|xpressio|
|00001040| 6e 73 3a 0a 0a 09 28 31 | 29 20 69 73 6f 6c 61 74 |ns:...(1|) isolat|
|00001050| 65 20 74 68 65 20 6c 6f | 6e 67 65 73 74 20 6d 65 |e the lo|ngest me|
|00001060| 74 61 63 68 61 72 61 63 | 74 65 72 2d 66 72 65 65 |tacharac|ter-free|
|00001070| 20 70 61 74 74 65 72 6e | 20 73 74 72 69 6e 67 20 | pattern| string |
|00001080| 76 69 61 20 74 68 65 0a | 09 20 20 20 20 22 72 65 |via the.|. "re|
|00001090| 67 6d 75 73 74 22 20 66 | 69 65 6c 64 20 70 72 6f |gmust" f|ield pro|
|000010a0| 76 69 64 65 64 20 62 79 | 20 48 2e 20 53 70 65 6e |vided by| H. Spen|
|000010b0| 63 65 72 27 73 20 72 65 | 67 63 6f 6d 70 28 29 20 |cer's re|gcomp() |
|000010c0| 72 6f 75 74 69 6e 65 2e | 0a 0a 09 20 20 20 20 28 |routine.|... (|
|000010d0| 4e 6f 6e 2d 6b 6f 73 68 | 65 72 2c 20 62 75 74 20 |Non-kosh|er, but |
|000010e0| 77 6f 72 74 68 20 6e 6f | 74 20 72 65 2d 69 6e 76 |worth no|t re-inv|
|000010f0| 65 6e 74 69 6e 67 20 74 | 68 65 20 77 68 65 65 6c |enting t|he wheel|
|00001100| 2e 0a 09 20 20 20 20 76 | 38 20 66 6f 6c 6b 73 20 |... v|8 folks |
|00001110| 6a 75 73 74 20 6d 69 67 | 68 74 20 68 61 76 65 20 |just mig|ht have |
|00001120| 74 6f 20 72 65 76 65 72 | 73 65 2d 65 6e 67 69 6e |to rever|se-engin|
|00001130| 65 65 72 20 53 70 65 6e | 63 65 72 27 73 0a 09 20 |eer Spen|cer's.. |
|00001140| 20 20 20 72 65 76 65 72 | 73 65 2d 65 6e 67 69 6e | rever|se-engin|
|00001150| 65 65 72 69 6e 67 20 74 | 6f 20 70 72 6f 76 69 64 |eering t|o provid|
|00001160| 65 20 65 71 75 69 76 61 | 6c 65 6e 74 20 66 75 6e |e equiva|lent fun|
|00001170| 63 74 69 6f 6e 61 6c 69 | 74 79 2e 0a 09 20 20 20 |ctionali|ty... |
|00001180| 20 59 6f 75 20 73 65 65 | 2c 20 74 68 65 72 65 20 | You see|, there |
|00001190| 61 72 65 20 6d 61 6e 79 | 20 6d 6f 72 65 20 73 69 |are many| more si|
|000011a0| 74 65 73 20 72 75 6e 6e | 69 6e 67 20 68 69 73 20 |tes runn|ing his |
|000011b0| 63 6f 64 65 20 74 68 61 | 6e 20 76 38 2e 0a 09 20 |code tha|n v8... |
|000011c0| 20 20 20 42 65 73 69 64 | 65 73 2c 20 77 65 20 65 | Besid|es, we e|
|000011d0| 6e 6a 6f 79 20 75 73 69 | 6e 67 20 72 65 67 65 78 |njoy usi|ng regex|
|000011e0| 70 72 20 74 65 63 68 6e | 6f 6c 6f 67 79 20 6f 6e |pr techn|ology on|
|000011f0| 20 69 74 73 65 6c 66 2e | 0a 0a 09 28 32 29 20 66 | itself.|...(2) f|
|00001200| 6f 72 20 22 73 68 6f 72 | 74 22 20 69 6e 70 75 74 |or "shor|t" input|
|00001210| 2c 20 73 75 62 6d 61 74 | 63 68 69 6e 67 20 6c 69 |, submat|ching li|
|00001220| 6e 65 73 20 61 72 65 20 | 70 61 73 73 65 64 20 74 |nes are |passed t|
|00001230| 6f 20 72 65 67 65 78 65 | 63 28 29 2e 0a 0a 09 28 |o regexe|c()....(|
|00001240| 33 29 20 66 6f 72 20 22 | 6c 6f 6e 67 22 20 69 6e |3) for "|long" in|
|00001250| 70 75 74 2c 20 73 74 61 | 72 74 20 75 70 20 61 20 |put, sta|rt up a |
|00001260| 73 74 61 6e 64 61 72 64 | 20 27 65 67 72 65 70 27 |standard| 'egrep'|
|00001270| 20 70 72 6f 63 65 73 73 | 20 76 69 61 0a 09 20 20 | process| via.. |
|00001280| 20 20 70 6f 70 65 6e 28 | 29 20 6f 72 20 65 71 75 | popen(|) or equ|
|00001290| 69 76 61 6c 65 6e 74 2e | 20 20 57 68 79 20 6e 6f |ivalent.| Why no|
|000012a0| 74 20 6a 75 73 74 20 75 | 73 65 20 72 65 67 65 78 |t just u|se regex|
|000012b0| 65 63 28 29 3f 20 20 55 | 6e 66 6f 72 74 75 6e 61 |ec()? U|nfortuna|
|000012c0| 74 65 6c 79 0a 09 20 20 | 20 20 66 6f 72 20 6f 75 |tely.. | for ou|
|000012d0| 72 20 61 70 70 6c 69 63 | 61 74 69 6f 6e 2c 20 53 |r applic|ation, S|
|000012e0| 70 65 6e 63 65 72 27 73 | 20 6f 74 68 65 72 77 69 |pencer's| otherwi|
|000012f0| 73 65 20 61 64 6d 69 72 | 61 62 6c 65 20 66 69 6e |se admir|able fin|
|00001300| 69 74 65 2d 73 74 61 74 | 65 0a 09 20 20 20 20 61 |ite-stat|e.. a|
|00001310| 75 74 6f 6d 61 74 6f 6e | 20 65 78 68 69 62 69 74 |utomaton| exhibit|
|00001320| 73 20 70 6f 6f 72 20 70 | 65 72 66 6f 72 6d 61 6e |s poor p|erforman|
|00001330| 63 65 20 66 6f 72 20 63 | 6f 6d 70 6c 65 78 20 65 |ce for c|omplex e|
|00001340| 78 70 72 65 73 73 69 6f | 6e 73 2e 0a 09 20 20 20 |xpressio|ns... |
|00001350| 20 53 65 74 74 69 6e 67 | 20 61 20 74 68 72 65 73 | Setting| a thres|
|00001360| 68 6f 6c 64 20 6f 6e 20 | 69 6e 70 75 74 20 6c 65 |hold on |input le|
|00001370| 6e 67 74 68 2c 20 74 68 | 6f 75 67 68 20 6e 6f 74 |ngth, th|ough not|
|00001380| 20 70 65 72 66 65 63 74 | 2c 20 68 65 6c 70 73 2e | perfect|, helps.|
|00001390| 0a 09 20 20 20 20 49 66 | 20 70 69 70 65 73 20 6f |.. If| pipes o|
|000013a0| 6e 20 55 6e 69 78 20 77 | 65 72 65 20 66 72 65 65 |n Unix w|ere free|
|000013b0| 2c 20 77 65 27 64 20 75 | 73 65 20 74 68 69 73 20 |, we'd u|se this |
|000013c0| 77 61 79 20 65 78 63 6c | 75 73 69 76 65 6c 79 2e |way excl|usively.|
|000013d0| 0a 09 20 20 20 20 55 6e | 74 69 6c 20 74 68 65 6e |.. Un|til then|
|000013e0| 2c 20 77 65 20 62 75 79 | 20 68 61 70 70 69 6e 65 |, we buy| happine|
|000013f0| 73 73 20 66 6f 72 20 74 | 68 6f 73 65 20 77 68 6f |ss for t|hose who|
|00001400| 20 6d 69 67 68 74 0a 0a | 09 09 09 65 67 72 65 70 | might..|...egrep|
|00001410| 20 73 74 75 66 66 20 2f | 75 73 72 2f 73 70 6f 6f | stuff /|usr/spoo|
|00001420| 6c 2f 6e 65 77 73 2f 6e | 65 74 2f 75 6e 69 78 2f |l/news/n|et/unix/|
|00001430| 2a 0a 0a 09 20 20 20 20 | 6f 72 20 6f 6e 20 6f 74 |*... |or on ot|
|00001440| 68 65 72 20 64 69 72 65 | 63 74 6f 72 69 65 73 20 |her dire|ctories |
|00001450| 66 75 6c 6c 20 6f 66 20 | 73 68 6f 72 74 20 66 69 |full of |short fi|
|00001460| 6c 65 73 2e 0a 0a 53 6f | 2c 0a 09 6e 65 77 65 67 |les...So|,..neweg|
|00001470| 72 65 70 20 2d 69 20 27 | 68 6f 65 2e 2a 67 27 20 |rep -i '|hoe.*g' |
|00001480| 09 20 20 20 20 77 6f 72 | 64 73 20 09 31 2e 32 20 |. wor|ds .1.2 |
|00001490| 20 31 2e 31 0a 09 09 09 | 09 09 20 09 7b 73 68 6f | 1.1....|.. .{sho|
|000014a0| 65 73 74 72 69 6e 67 2c | 53 68 6f 65 6e 62 65 72 |estring,|Shoenber|
|000014b0| 67 7d 0a 09 6e 65 77 65 | 67 72 65 70 20 27 28 61 |g}..newe|grep '(a|
|000014c0| 7c 62 29 2e 2a 7a 7a 2e | 2a 5b 6f 64 5d 24 27 20 ||b).*zz.|*[od]$' |
|000014d0| 77 6f 72 64 73 20 09 31 | 2e 35 20 20 31 2e 31 0a |words .1|.5 1.1.|
|000014e0| 09 09 09 09 09 20 09 7b | 62 6c 69 7a 7a 61 72 64 |..... .{|blizzard|
|000014f0| 2c 62 75 7a 7a 77 6f 72 | 64 2c 70 61 6c 61 7a 7a |,buzzwor|d,palazz|
|00001500| 6f 7d 0a 09 6f 6c 64 65 | 67 72 65 70 20 09 09 09 |o}..olde|grep ...|
|00001510| 09 36 2e 33 20 20 31 2e | 34 0a 62 75 74 2c 0a 09 |.6.3 1.|4.but,..|
|00001520| 7b 6e 65 77 2c 6f 6c 64 | 7d 65 67 72 65 70 20 2d |{new,old|}egrep -|
|00001530| 63 20 27 28 66 69 72 73 | 74 7c 73 65 63 6f 6e 64 |c '(firs|t|second|
|00001540| 29 27 09 73 69 6d 69 6c | 61 72 20 74 69 6d 65 73 |)'.simil|ar times|
|00001550| 20 28 6e 6f 20 69 73 6f | 6c 61 74 65 29 0a 0a 41 | (no iso|late)..A|
|00001560| 67 61 69 6e 2c 20 77 65 | 20 73 74 72 65 73 73 20 |gain, we| stress |
|00001570| 74 68 61 74 20 67 69 76 | 65 6e 20 74 68 65 20 64 |that giv|en the d|
|00001580| 69 66 66 65 72 65 6e 74 | 20 6e 61 74 75 72 65 20 |ifferent| nature |
|00001590| 6f 66 20 74 68 65 20 73 | 69 6d 75 6c 61 74 69 6f |of the s|imulatio|
|000015a0| 6e 73 20 6f 66 20 74 68 | 65 20 74 77 6f 0a 6e 6f |ns of th|e two.no|
|000015b0| 6e 64 65 74 65 72 6d 69 | 6e 69 73 74 69 63 20 72 |ndetermi|nistic r|
|000015c0| 65 67 2e 20 65 78 70 72 | 2e 20 73 74 61 74 65 2d |eg. expr|. state-|
|000015d0| 6d 61 63 68 69 6e 65 73 | 20 28 6f 6e 65 20 66 75 |machines| (one fu|
|000015e0| 6e 63 74 69 6f 6e 6c 65 | 73 73 29 2c 20 63 61 73 |nctionle|ss), cas|
|000015f0| 65 73 20 63 61 6e 20 62 | 65 0a 22 63 6f 6f 6b 65 |es can b|e."cooke|
|00001600| 64 22 20 74 6f 20 73 68 | 6f 77 20 74 68 69 6e 67 |d" to sh|ow thing|
|00001610| 73 20 69 6e 20 61 20 62 | 61 64 20 6c 69 67 68 74 |s in a b|ad light|
|00001620| 2c 20 73 6f 20 61 20 68 | 79 62 72 69 64 20 69 73 |, so a h|ybrid is|
|00001630| 20 77 61 72 72 61 6e 74 | 65 64 2e 0a 57 65 20 63 | warrant|ed..We c|
|00001640| 61 6e 20 67 65 6e 65 72 | 61 6c 6c 79 20 64 6f 20 |an gener|ally do |
|00001650| 62 65 74 74 65 72 20 69 | 6e 63 6f 72 70 6f 72 61 |better i|ncorpora|
|00001660| 74 69 6e 67 20 74 68 65 | 20 42 6f 79 65 72 2d 4d |ting the| Boyer-M|
|00001670| 6f 6f 72 65 20 61 6c 67 | 6f 72 69 74 68 6d 20 64 |oore alg|orithm d|
|00001680| 69 72 65 63 74 6c 79 0a | 69 6e 74 6f 20 74 68 65 |irectly.|into the|
|00001690| 20 41 54 26 54 20 63 6f | 64 65 2e 20 20 46 6f 72 | AT&T co|de. For|
|000016a0| 20 74 68 65 20 6c 61 73 | 74 20 65 78 61 6d 70 6c | the las|t exampl|
|000016b0| 65 2c 20 74 68 65 20 61 | 62 73 74 72 61 63 74 69 |e, the a|bstracti|
|000016c0| 6f 6e 0a 0a 09 28 65 67 | 72 65 70 20 66 69 72 73 |on...(eg|rep firs|
|000016d0| 74 20 77 6f 72 64 73 20 | 26 3b 20 65 67 72 65 70 |t words |&; egrep|
|000016e0| 20 73 65 63 6f 6e 64 20 | 77 6f 72 64 73 29 20 7c | second |words) ||
|000016f0| 20 73 6f 72 74 20 2d 75 | 20 7c 20 77 63 0a 0a 69 | sort -u| | wc..i|
|00001700| 64 65 61 6c 6c 79 20 77 | 6f 75 6c 64 20 77 6f 72 |deally w|ould wor|
|00001710| 6b 20 62 65 74 74 65 72 | 20 6f 6e 20 61 20 70 61 |k better| on a pa|
|00001720| 72 61 6c 6c 65 6c 20 6d | 61 63 68 69 6e 65 2c 20 |rallel m|achine, |
|00001730| 62 75 74 20 69 66 20 79 | 6f 75 27 72 65 20 65 78 |but if y|ou're ex|
|00001740| 70 65 63 74 69 6e 67 0a | 73 6f 6d 65 74 68 69 6e |pecting.|somethin|
|00001750| 67 20 61 73 20 61 6d 61 | 7a 69 6e 67 20 69 6e 20 |g as ama|zing in |
|00001760| 74 68 69 73 20 64 72 61 | 66 74 20 61 73 2c 20 73 |this dra|ft as, s|
|00001770| 61 79 2c 20 4d 6f 72 77 | 65 6e 20 42 2e 20 54 68 |ay, Morw|en B. Th|
|00001780| 69 73 74 6c 65 74 68 77 | 61 69 74 65 27 73 20 35 |istlethw|aite's 5|
|00001790| 32 2d 6d 6f 76 65 0a 52 | 75 62 69 6b 27 73 20 43 |2-move.R|ubik's C|
|000017a0| 75 62 65 20 73 6f 6c 75 | 74 69 6f 6e 2c 20 79 6f |ube solu|tion, yo|
|000017b0| 75 27 72 65 20 69 6e 20 | 74 68 65 20 77 72 6f 6e |u're in |the wron|
|000017c0| 67 20 70 6c 61 63 65 2e | 0a 0a 20 20 20 20 20 41 |g place.|.. A|
|000017d0| 62 6f 75 74 20 6f 70 74 | 69 6f 6e 73 20 2d 2d 20 |bout opt|ions -- |
|000017e0| 73 79 73 74 65 6d 20 56 | 20 6f 6e 65 73 20 61 72 |system V| ones ar|
|000017f0| 65 20 73 75 70 70 6f 72 | 74 65 64 20 28 2d 63 2c |e suppor|ted (-c,|
|00001800| 20 2d 6c 2c 20 62 6f 6e | 75 73 20 2d 69 20 66 6f | -l, bon|us -i fo|
|00001810| 72 20 42 53 44 29 3b 0a | 74 68 65 20 27 65 67 72 |r BSD);.|the 'egr|
|00001820| 65 70 27 20 68 65 72 65 | 20 6a 75 73 74 20 68 61 |ep' here| just ha|
|00001830| 6e 64 73 20 6f 66 66 20 | 70 61 74 74 65 72 6e 73 |nds off |patterns|
|00001840| 20 74 6f 20 6f 6c 64 20 | 63 6f 64 65 20 66 6f 72 | to old |code for|
|00001850| 20 74 68 69 6e 67 73 20 | 6c 69 6b 65 20 2d 6e 2c | things |like -n,|
|00001860| 20 2d 62 2c 0a 2d 76 2c | 20 61 6e 64 20 6d 75 6c | -b,.-v,| and mul|
|00001870| 74 69 70 6c 65 20 70 61 | 74 74 65 72 6e 73 2e 20 |tiple pa|tterns. |
|00001880| 20 41 73 20 61 20 62 6f | 6e 65 20 74 6f 20 74 68 | As a bo|ne to th|
|00001890| 72 6f 77 20 74 6f 20 74 | 68 65 20 65 6e 65 6d 69 |row to t|he enemi|
|000018a0| 65 73 20 6f 66 20 74 68 | 65 20 63 61 74 2d 76 0a |es of th|e cat-v.|
|000018b0| 73 63 68 6f 6f 6c 2c 20 | 74 68 65 72 65 20 69 73 |school, |there is|
|000018c0| 20 61 20 2d 68 20 28 68 | 61 6c 74 20 61 66 74 65 | a -h (h|alt afte|
|000018d0| 72 20 70 72 69 6e 74 69 | 6e 67 20 66 69 72 73 74 |r printi|ng first|
|000018e0| 20 6d 61 74 63 68 29 2c | 20 62 75 74 20 77 65 20 | match),| but we |
|000018f0| 64 6f 6e 27 74 20 74 61 | 6c 6b 0a 61 62 6f 75 74 |don't ta|lk.about|
|00001900| 20 69 74 20 6d 75 63 68 | 2e 20 20 4d 75 6c 74 69 | it much|. Multi|
|00001910| 70 6c 65 20 70 61 74 74 | 65 72 6e 73 20 63 61 6e |ple patt|erns can|
|00001920| 20 64 6f 6e 65 20 61 6c | 61 20 27 62 6d 27 20 62 | done al|a 'bm' b|
|00001930| 75 74 20 6c 61 7a 69 6e | 65 73 73 20 69 6e 20 74 |ut lazin|ess in t|
|00001940| 68 65 0a 70 72 65 73 65 | 6e 63 65 20 6f 66 20 6c |he.prese|nce of l|
|00001950| 61 63 6b 20 6f 66 20 6b | 6e 6f 77 6c 65 64 67 65 |ack of k|nowledge|
|00001960| 20 6f 66 20 77 68 65 72 | 65 20 27 66 67 72 65 70 | of wher|e 'fgrep|
|00001970| 27 20 77 69 6e 73 20 68 | 61 73 20 70 72 65 76 61 |' wins h|as preva|
|00001980| 69 6c 65 64 20 66 6f 72 | 20 76 65 72 73 69 6f 6e |iled for| version|
|00001990| 20 31 2e 0a 0a 20 20 20 | 20 20 50 65 72 73 6f 6e | 1... | Person|
|000019a0| 61 6c 6c 79 20 49 20 66 | 65 65 6c 20 74 68 61 74 |ally I f|eel that|
|000019b0| 20 61 64 61 70 74 69 6e | 67 20 28 22 69 6e 74 65 | adaptin|g ("inte|
|000019c0| 72 6e 61 74 69 6f 6e 61 | 6c 69 7a 69 6e 67 22 29 |rnationa|lizing")|
|000019d0| 20 74 68 65 20 27 65 67 | 72 65 70 27 20 65 66 66 | the 'eg|rep' eff|
|000019e0| 6f 72 74 0a 66 6f 72 20 | 74 77 6f 2d 62 79 74 65 |ort.for |two-byte|
|000019f0| 20 4b 61 6e 6a 69 20 69 | 73 20 46 41 52 20 6d 6f | Kanji i|s FAR mo|
|00001a00| 72 65 20 69 6d 70 6f 72 | 74 61 6e 74 20 74 68 61 |re impor|tant tha|
|00001a10| 6e 20 74 77 65 65 6b 69 | 6e 67 20 6f 70 74 69 6f |n tweeki|ng optio|
|00001a20| 6e 73 20 6f 72 20 74 72 | 61 64 65 6f 66 66 73 2c |ns or tr|adeoffs,|
|00001a30| 0a 73 6f 20 66 6f 72 20 | 79 6f 75 20 6c 61 72 67 |.so for |you larg|
|00001a40| 65 2d 61 6c 70 68 61 62 | 65 74 20 42 6f 79 65 72 |e-alphab|et Boyer|
|00001a50| 2d 4d 6f 6f 72 65 20 61 | 6c 67 6f 72 69 74 68 6d |-Moore a|lgorithm|
|00001a60| 20 73 70 65 63 69 61 6c | 69 73 74 73 2c 20 73 65 | special|ists, se|
|00001a70| 6e 64 20 69 64 65 61 73 | 0a 74 68 69 73 20 77 61 |nd ideas|.this wa|
|00001a80| 79 2e 0a 20 20 20 20 20 | 0a 20 20 20 20 20 46 75 |y.. |. Fu|
|00001a90| 72 74 68 65 72 20 68 69 | 73 74 6f 72 69 63 61 6c |rther hi|storical|
|00001aa0| 2f 70 68 69 6c 6f 73 6f | 70 68 69 63 61 6c 20 63 |/philoso|phical c|
|00001ab0| 6f 6d 6d 65 6e 74 73 20 | 66 6f 6c 6c 6f 77 20 69 |omments |follow i|
|00001ac0| 6e 20 74 68 65 20 73 65 | 71 75 65 6c 2e 0a 0a 20 |n the se|quel... |
|00001ad0| 20 20 20 20 4a 61 6d 65 | 73 20 41 2e 20 57 6f 6f | Jame|s A. Woo|
|00001ae0| 64 73 20 28 61 6d 65 73 | 21 6a 61 77 29 0a 20 20 |ds (ames|!jaw). |
|00001af0| 20 20 20 4e 41 53 41 20 | 41 6d 65 73 20 52 65 73 | NASA |Ames Res|
|00001b00| 65 61 72 63 68 20 43 65 | 6e 74 65 72 0a 0a 53 48 |earch Ce|nter..SH|
|00001b10| 41 52 5f 45 4f 46 0a 69 | 66 20 74 65 73 74 20 36 |AR_EOF.i|f test 6|
|00001b20| 31 30 34 20 2d 6e 65 20 | 22 60 77 63 20 2d 63 20 |104 -ne |"`wc -c |
|00001b30| 3c 20 27 70 65 70 34 67 | 72 65 70 2e 31 27 60 22 |< 'pep4g|rep.1'`"|
|00001b40| 0a 74 68 65 6e 0a 09 65 | 63 68 6f 20 73 68 61 72 |.then..e|cho shar|
|00001b50| 3a 20 65 72 72 6f 72 20 | 74 72 61 6e 73 6d 69 74 |: error |transmit|
|00001b60| 74 69 6e 67 20 22 27 70 | 65 70 34 67 72 65 70 2e |ting "'p|ep4grep.|
|00001b70| 31 27 22 20 27 28 73 68 | 6f 75 6c 64 20 68 61 76 |1'" '(sh|ould hav|
|00001b80| 65 20 62 65 65 6e 20 36 | 31 30 34 20 63 68 61 72 |e been 6|104 char|
|00001b90| 61 63 74 65 72 73 29 27 | 0a 66 69 0a 66 69 0a 65 |acters)'|.fi.fi.e|
|00001ba0| 63 68 6f 20 73 68 61 72 | 3a 20 65 78 74 72 61 63 |cho shar|: extrac|
|00001bb0| 74 69 6e 67 20 22 27 70 | 65 70 34 67 72 65 70 2e |ting "'p|ep4grep.|
|00001bc0| 32 27 22 20 27 28 34 36 | 32 33 20 63 68 61 72 61 |2'" '(46|23 chara|
|00001bd0| 63 74 65 72 73 29 27 0a | 69 66 20 74 65 73 74 20 |cters)'.|if test |
|00001be0| 2d 66 20 27 70 65 70 34 | 67 72 65 70 2e 32 27 0a |-f 'pep4|grep.2'.|
|00001bf0| 74 68 65 6e 0a 09 65 63 | 68 6f 20 73 68 61 72 3a |then..ec|ho shar:|
|00001c00| 20 77 69 6c 6c 20 6e 6f | 74 20 6f 76 65 72 2d 77 | will no|t over-w|
|00001c10| 72 69 74 65 20 65 78 69 | 73 74 69 6e 67 20 66 69 |rite exi|sting fi|
|00001c20| 6c 65 20 22 27 70 65 70 | 34 67 72 65 70 2e 32 27 |le "'pep|4grep.2'|
|00001c30| 22 0a 65 6c 73 65 0a 63 | 61 74 20 3c 3c 20 5c 53 |".else.c|at << \S|
|00001c40| 48 41 52 5f 45 4f 46 20 | 3e 20 27 70 65 70 34 67 |HAR_EOF |> 'pep4g|
|00001c50| 72 65 70 2e 32 27 0a 3e | 46 72 6f 6d 20 70 6f 73 |rep.2'.>|From pos|
|00001c60| 74 6e 65 77 73 20 54 75 | 65 20 4d 61 72 20 31 38 |tnews Tu|e Mar 18|
|00001c70| 20 31 38 3a 30 35 3a 32 | 32 20 31 39 38 36 0a 53 | 18:05:2|2 1986.S|
|00001c80| 75 62 6a 65 63 74 3a 20 | 4d 6f 72 65 20 50 65 70 |ubject: |More Pep|
|00001c90| 20 66 6f 72 20 42 6f 79 | 65 72 2d 4d 6f 6f 72 65 | for Boy|er-Moore|
|00001ca0| 20 47 72 65 70 20 28 70 | 61 72 74 20 32 20 6f 66 | Grep (p|art 2 of|
|00001cb0| 20 32 29 0a 4e 65 77 73 | 67 72 6f 75 70 73 3a 20 | 2).News|groups: |
|00001cc0| 6e 65 74 2e 75 6e 69 78 | 0a 0a 23 20 20 22 47 72 |net.unix|..# "Gr|
|00001cd0| 61 74 69 61 6e 6f 20 73 | 70 65 61 6b 73 20 61 6e |atiano s|peaks an|
|00001ce0| 20 69 6e 66 69 6e 69 74 | 65 20 64 65 61 6c 20 6f | infinit|e deal o|
|00001cf0| 66 20 6e 6f 74 68 69 6e | 67 2c 20 6d 6f 72 65 20 |f nothin|g, more |
|00001d00| 74 68 61 6e 20 61 6e 79 | 20 6d 61 6e 20 69 6e 20 |than any| man in |
|00001d10| 61 6c 6c 0a 20 20 20 6f | 66 20 56 65 6e 69 63 65 |all. o|f Venice|
|00001d20| 2e 20 20 48 69 73 20 72 | 65 61 73 6f 6e 73 20 61 |. His r|easons a|
|00001d30| 72 65 20 61 73 20 74 77 | 6f 20 67 72 61 69 6e 73 |re as tw|o grains|
|00001d40| 20 6f 66 20 77 68 65 61 | 74 20 68 69 64 20 69 6e | of whea|t hid in|
|00001d50| 20 74 77 6f 20 62 75 73 | 68 65 6c 73 20 6f 66 0a | two bus|hels of.|
|00001d60| 20 20 20 63 68 61 66 66 | 3a 20 20 79 6f 75 20 73 | chaff|: you s|
|00001d70| 68 61 6c 6c 20 73 65 65 | 6b 20 61 6c 6c 20 64 61 |hall see|k all da|
|00001d80| 79 20 65 72 65 20 79 6f | 75 20 66 69 6e 64 20 74 |y ere yo|u find t|
|00001d90| 68 65 6d 2c 20 74 68 65 | 79 20 61 72 65 20 6e 6f |hem, the|y are no|
|00001da0| 74 20 77 6f 72 74 68 0a | 20 20 20 74 68 65 20 73 |t worth.| the s|
|00001db0| 65 61 72 63 68 2e 22 20 | 20 2d 2d 20 53 68 61 6b |earch." | -- Shak|
|00001dc0| 65 73 70 65 61 72 65 2c | 20 4d 65 72 63 68 61 6e |espeare,| Merchan|
|00001dd0| 74 20 6f 66 20 56 65 6e | 69 63 65 0a 0a 2e 2e 2e |t of Ven|ice.....|
|00001de0| 20 6f 72 2c 20 70 61 72 | 74 20 32 2c 20 22 52 65 | or, par|t 2, "Re|
|00001df0| 61 63 68 20 6f 75 74 20 | 61 6e 64 20 42 6f 79 65 |ach out |and Boye|
|00001e00| 72 2d 4d 6f 6f 72 65 20 | 45 67 72 65 70 20 53 6f |r-Moore |Egrep So|
|00001e10| 6d 65 6f 6e 65 22 0a 0a | 20 20 20 20 20 4d 61 79 |meone"..| May|
|00001e20| 62 65 20 79 6f 75 20 6e | 65 76 65 72 20 75 73 65 |be you n|ever use|
|00001e30| 20 27 67 72 65 70 27 2e | 20 20 54 68 65 6e 20 69 | 'grep'.| Then i|
|00001e40| 67 6e 6f 72 65 20 74 68 | 69 73 2e 20 20 42 75 74 |gnore th|is. But|
|00001e50| 20 69 66 20 79 6f 75 20 | 64 6f 2c 20 77 68 79 20 | if you |do, why |
|00001e60| 6e 6f 74 0a 75 73 65 20 | 74 68 65 20 62 65 73 74 |not.use |the best|
|00001e70| 20 61 6c 67 6f 72 69 74 | 68 6d 3f 20 20 53 65 72 | algorit|hm? Ser|
|00001e80| 69 6f 75 73 20 61 64 64 | 69 63 74 73 20 6b 6e 6f |ious add|icts kno|
|00001e90| 77 20 74 68 61 74 20 66 | 6f 72 20 75 6e 73 74 72 |w that f|or unstr|
|00001ea0| 75 63 74 75 72 65 64 20 | 79 65 74 0a 73 74 61 62 |uctured |yet.stab|
|00001eb0| 6c 65 20 74 65 78 74 2c | 20 42 2d 74 72 65 65 73 |le text,| B-trees|
|00001ec0| 20 61 72 65 20 75 73 65 | 64 20 66 6f 72 20 73 70 | are use|d for sp|
|00001ed0| 65 65 64 2c 20 6f 72 20 | 73 6f 6d 65 74 68 69 6e |eed, or |somethin|
|00001ee0| 67 20 6c 69 6b 65 20 4c | 65 73 6b 27 73 20 6e 69 |g like L|esk's ni|
|00001ef0| 66 74 79 0a 28 61 6e 64 | 20 75 6e 61 76 61 69 6c |fty.(and| unavail|
|00001f00| 61 62 6c 65 29 20 27 67 | 72 61 62 27 20 73 75 69 |able) 'g|rab' sui|
|00001f10| 74 65 20 66 6f 72 20 69 | 6e 76 65 72 74 65 64 20 |te for i|nverted |
|00001f20| 66 69 6c 65 73 20 61 72 | 65 20 77 61 79 73 20 74 |files ar|e ways t|
|00001f30| 6f 20 67 6f 2e 20 20 42 | 61 72 72 69 6e 67 20 66 |o go. B|arring f|
|00001f40| 69 6c 65 0a 69 6e 76 65 | 72 73 69 6f 6e 20 64 61 |ile.inve|rsion da|
|00001f50| 65 6d 6f 6e 73 20 66 6f | 72 20 6e 65 74 6e 65 77 |emons fo|r netnew|
|00001f60| 73 20 61 6e 64 20 6f 74 | 68 65 72 20 65 70 68 65 |s and ot|her ephe|
|00001f70| 6d 65 72 61 2c 20 77 65 | 20 61 72 65 20 6c 69 6d |mera, we| are lim|
|00001f80| 69 74 65 64 20 74 6f 20 | 74 68 65 0a 70 72 65 73 |ited to |the.pres|
|00001f90| 65 6e 74 20 69 6d 70 72 | 6f 76 65 6d 65 6e 74 73 |ent impr|ovements|
|00001fa0| 2e 0a 0a 20 20 20 20 20 | 50 72 6f 70 65 72 20 73 |... |Proper s|
|00001fb0| 6b 65 70 74 69 63 73 20 | 73 68 6f 75 6c 64 20 71 |keptics |should q|
|00001fc0| 75 65 73 74 69 6f 6e 20 | 77 68 79 20 61 20 6e 65 |uestion |why a ne|
|00001fd0| 61 72 6c 79 20 49 2f 4f | 2d 62 6f 75 6e 64 20 70 |arly I/O|-bound p|
|00001fe0| 72 6f 67 72 61 6d 0a 28 | 62 75 74 20 6e 6f 74 20 |rogram.(|but not |
|00001ff0| 66 6f 72 20 61 6e 79 20 | 43 50 55 20 77 69 74 68 |for any |CPU with|
|00002000| 20 6c 65 73 73 20 74 68 | 61 6e 20 74 68 65 20 70 | less th|an the p|
|00002010| 6f 77 65 72 20 6f 66 20 | 61 20 37 38 30 2c 20 61 |ower of |a 780, a|
|00002020| 6c 61 73 29 20 73 68 6f | 75 6c 64 20 62 65 0a 6d |las) sho|uld be.m|
|00002030| 61 64 65 20 6d 6f 72 65 | 20 73 6f 2e 20 20 54 68 |ade more| so. Th|
|00002040| 65 20 71 75 65 73 74 69 | 6f 6e 20 77 61 73 20 70 |e questi|on was p|
|00002050| 6f 73 65 64 20 69 6e 20 | 42 20 26 20 4d 27 73 20 |osed in |B & M's |
|00002060| 63 6c 61 73 73 69 63 20 | 31 39 37 38 20 43 41 43 |classic |1978 CAC|
|00002070| 4d 0a 70 61 70 65 72 20 | 2d 2d 20 74 68 65 20 61 |M.paper |-- the a|
|00002080| 6e 73 77 65 72 20 74 68 | 65 6e 20 77 61 73 20 74 |nswer th|en was t|
|00002090| 6f 20 66 72 65 65 20 75 | 70 20 6d 6f 72 65 20 43 |o free u|p more C|
|000020a0| 50 55 20 63 79 63 6c 65 | 73 20 66 6f 72 20 74 69 |PU cycle|s for ti|
|000020b0| 6d 65 73 68 61 72 69 6e | 67 2e 0a 4e 6f 77 2c 20 |mesharin|g..Now, |
|000020c0| 6f 75 72 20 6d 6f 74 69 | 76 61 74 69 6f 6e 73 20 |our moti|vations |
|000020d0| 61 72 65 20 6d 6f 72 65 | 20 6d 75 6e 64 61 6e 65 |are more| mundane|
|000020e0| 20 28 77 65 20 77 6f 6e | 27 74 20 68 61 76 65 20 | (we won|'t have |
|000020f0| 64 65 73 6b 74 6f 70 20 | 35 20 4d 49 50 20 6d 61 |desktop |5 MIP ma|
|00002100| 63 68 69 6e 65 73 0a 66 | 6f 72 20 61 6e 6f 74 68 |chines.f|or anoth|
|00002110| 65 72 20 79 65 61 72 29 | 2c 20 62 75 74 20 6e 6f |er year)|, but no|
|00002120| 74 20 6f 6e 6c 79 20 74 | 68 61 74 2c 20 77 65 27 |t only t|hat, we'|
|00002130| 76 65 20 64 69 73 63 6f | 76 65 72 65 64 20 74 68 |ve disco|vered th|
|00002140| 61 74 20 74 68 65 20 43 | 72 61 79 20 32 27 73 0a |at the C|ray 2's.|
|00002150| 73 74 61 6e 64 61 72 64 | 20 27 65 67 72 65 70 27 |standard| 'egrep'|
|00002160| 20 69 73 20 61 6c 73 6f | 20 76 65 72 79 20 61 6e | is also| very an|
|00002170| 65 6d 69 63 2c 20 70 65 | 72 66 6f 72 6d 69 6e 67 |emic, pe|rforming|
|00002180| 20 38 2d 31 32 20 74 69 | 6d 65 73 20 61 73 20 77 | 8-12 ti|mes as w|
|00002190| 6f 72 73 65 20 61 73 20 | 6f 75 72 73 0a 6f 6e 20 |orse as |ours.on |
|000021a0| 73 69 6d 70 6c 65 20 70 | 61 74 74 65 72 6e 73 2e |simple p|atterns.|
|000021b0| 20 20 46 6f 72 20 73 68 | 61 6d 65 2c 20 65 73 70 | For sh|ame, esp|
|000021c0| 65 63 69 61 6c 6c 79 20 | 73 69 6e 63 65 20 68 65 |ecially |since he|
|000021d0| 61 72 69 6e 67 20 6f 66 | 20 74 68 65 20 72 75 6d |aring of| the rum|
|000021e0| 6f 72 20 74 68 61 74 0a | 63 65 72 74 61 69 6e 20 |or that.|certain |
|000021f0| 67 72 6f 75 70 20 74 68 | 65 6f 72 69 73 74 73 20 |group th|eorists |
|00002200| 68 61 76 65 20 61 20 73 | 65 61 72 63 68 20 61 70 |have a s|earch ap|
|00002210| 70 6c 69 63 61 74 69 6f | 6e 20 72 65 61 64 79 20 |plicatio|n ready |
|00002220| 66 6f 72 20 74 65 73 74 | 69 6e 67 2e 0a 42 6f 79 |for test|ing..Boy|
|00002230| 65 72 2d 4d 6f 6f 72 65 | 20 63 6f 75 6c 64 20 66 |er-Moore| could f|
|00002240| 69 6c 6c 20 69 6e 20 75 | 6e 74 69 6c 20 61 20 43 |ill in u|ntil a C|
|00002250| 72 61 79 20 76 65 63 74 | 6f 72 69 7a 69 6e 67 20 |ray vect|orizing |
|00002260| 43 20 63 6f 6d 70 69 6c | 65 72 20 73 68 6f 77 73 |C compil|er shows|
|00002270| 20 75 70 2e 0a 53 68 65 | 65 72 20 73 70 65 65 64 | up..She|er speed|
|00002280| 20 66 6f 72 20 6d 61 63 | 68 69 6e 65 73 20 77 68 | for mac|hines wh|
|00002290| 6f 73 65 20 66 69 6c 65 | 73 79 73 74 65 6d 73 20 |ose file|systems |
|000022a0| 61 72 65 20 63 61 63 68 | 65 64 20 69 6e 20 6d 65 |are cach|ed in me|
|000022b0| 6d 6f 72 79 20 69 73 20 | 6e 69 63 65 20 74 6f 6f |mory is |nice too|
|000022c0| 2e 0a 0a 20 20 20 20 20 | 41 20 71 75 69 63 6b 2d |... |A quick-|
|000022d0| 61 6e 64 2d 64 69 72 74 | 79 20 72 75 6e 64 6f 77 |and-dirt|y rundow|
|000022e0| 6e 20 6f 66 20 74 68 65 | 20 64 65 62 74 73 20 74 |n of the| debts t|
|000022f0| 6f 20 77 68 69 63 68 20 | 74 68 65 20 6e 65 77 20 |o which |the new |
|00002300| 68 79 62 72 69 64 20 70 | 61 79 73 0a 6e 6f 77 20 |hybrid p|ays.now |
|00002310| 66 6f 6c 6c 6f 77 73 2e | 0a 0a 09 54 68 6f 6d 70 |follows.|...Thomp|
|00002320| 73 6f 6e 2c 20 4b 2e 20 | 54 2e 20 28 43 41 43 4d |son, K. |T. (CACM|
|00002330| 2c 20 4e 6f 76 65 6d 62 | 65 72 20 31 39 36 38 29 |, Novemb|er 1968)|
|00002340| 3a 0a 09 09 52 65 67 75 | 6c 61 72 20 45 78 70 72 |:...Regu|lar Expr|
|00002350| 65 73 73 69 6f 6e 20 53 | 65 61 72 63 68 20 41 6c |ession S|earch Al|
|00002360| 67 6f 72 69 74 68 6d 2e | 20 20 41 73 20 75 73 75 |gorithm.| As usu|
|00002370| 61 6c 2c 20 6f 62 76 69 | 6f 75 73 0a 09 09 6f 6e |al, obvi|ous...on|
|00002380| 63 65 20 79 6f 75 20 75 | 6e 64 65 72 73 74 61 6e |ce you u|nderstan|
|00002390| 64 20 69 74 2e 20 20 54 | 68 65 20 63 75 72 72 65 |d it. T|he curre|
|000023a0| 6e 74 20 27 65 67 72 65 | 70 27 2e 20 20 53 74 69 |nt 'egre|p'. Sti|
|000023b0| 6c 6c 0a 09 09 75 73 65 | 66 75 6c 20 61 73 20 61 |ll...use|ful as a|
|000023c0| 20 62 61 73 65 2e 20 20 | 41 62 73 74 72 61 63 74 | base. |Abstract|
|000023d0| 65 64 20 62 79 20 41 68 | 6f 2f 55 6c 6c 6d 61 6e |ed by Ah|o/Ullman|
|000023e0| 20 61 73 20 41 6c 67 6f | 72 69 74 68 6d 0a 09 09 | as Algo|rithm...|
|000023f0| 39 2e 31 20 69 6e 20 44 | 65 73 69 67 6e 20 61 6e |9.1 in D|esign an|
|00002400| 64 20 41 6e 61 6c 79 73 | 69 73 20 6f 66 20 43 6f |d Analys|is of Co|
|00002410| 6d 70 75 74 65 72 20 41 | 6c 67 6f 72 69 74 68 6d |mputer A|lgorithm|
|00002420| 73 2e 0a 0a 09 42 6f 79 | 65 72 2f 4d 6f 6f 72 65 |s....Boy|er/Moore|
|00002430| 3a 0a 09 09 4e 6f 74 20 | 71 75 69 74 65 20 70 72 |:...Not |quite pr|
|00002440| 65 2d 55 6e 69 78 2e 20 | 20 4f 68 20 77 65 6c 6c |e-Unix. | Oh well|
|00002450| 2e 20 20 4d 6f 64 65 72 | 6e 20 64 65 73 69 67 6e |. Moder|n design|
|00002460| 65 72 73 20 73 68 6f 75 | 6c 64 0a 09 09 6b 6e 6f |ers shou|ld...kno|
|00002470| 77 20 62 65 74 74 65 72 | 20 6e 6f 77 2c 20 69 66 |w better| now, if|
|00002480| 20 74 68 65 79 20 77 61 | 6e 74 20 74 68 65 69 72 | they wa|nt their|
|00002490| 20 73 74 75 66 66 20 74 | 6f 20 67 65 74 20 6f 75 | stuff t|o get ou|
|000024a0| 74 20 74 68 65 72 65 2e | 0a 09 09 42 79 20 74 68 |t there.|...By th|
|000024b0| 65 20 77 61 79 2c 20 49 | 20 68 61 76 65 6e 27 74 |e way, I| haven't|
|000024c0| 20 75 73 65 64 20 64 65 | 6c 74 61 32 20 28 6f 72 | used de|lta2 (or|
|000024d0| 20 31 29 20 73 69 6e 63 | 65 20 74 68 65 20 4f 28 | 1) sinc|e the O(|
|000024e0| 6d 6e 29 20 63 61 73 65 | 0a 09 09 63 61 73 65 20 |mn) case|...case |
|000024f0| 64 6f 65 73 6e 27 74 20 | 63 6f 6d 65 20 75 70 20 |doesn't |come up |
|00002500| 74 6f 6f 20 6f 66 74 65 | 6e 2e 20 20 53 75 72 65 |too ofte|n. Sure|
|00002510| 20 4b 6e 75 74 68 20 73 | 74 6f 6f 64 20 6f 6e 20 | Knuth s|tood on |
|00002520| 68 69 73 20 68 65 61 64 | 0a 09 09 74 6f 20 62 65 |his head|...to be|
|00002530| 74 74 65 72 20 74 68 65 | 20 6c 69 6e 65 61 72 69 |tter the| lineari|
|00002540| 74 79 2c 20 62 75 74 20 | 68 69 73 20 70 72 6f 6f |ty, but |his proo|
|00002550| 66 20 68 61 64 20 61 20 | 62 75 67 20 69 6e 20 69 |f had a |bug in i|
|00002560| 74 20 75 6e 74 69 6c 0a | 09 09 74 68 65 20 31 39 |t until.|..the 19|
|00002570| 38 30 20 53 49 41 4d 20 | 4a 2e 20 43 6f 6d 70 75 |80 SIAM |J. Compu|
|00002580| 74 2e 20 72 65 74 72 61 | 63 74 69 6f 6e 2e 20 20 |t. retra|ction. |
|00002590| 57 6f 75 6c 64 20 79 6f | 75 20 77 61 6e 74 20 74 |Would yo|u want t|
|000025a0| 6f 20 63 6f 64 65 0a 09 | 09 73 6f 6d 65 74 68 69 |o code..|.somethi|
|000025b0| 6e 67 20 74 68 61 74 20 | 65 76 65 6e 20 4b 6e 75 |ng that |even Knu|
|000025c0| 74 68 20 74 72 69 70 73 | 20 75 70 20 6f 6e 3f 0a |th trips| up on?.|
|000025d0| 0a 20 09 09 4e 6f 77 20 | 74 6f 20 61 73 73 75 61 |. ..Now |to assua|
|000025e0| 67 65 20 6e 61 67 67 69 | 6e 67 20 66 65 65 6c 69 |ge naggi|ng feeli|
|000025f0| 6e 67 73 20 74 68 61 74 | 20 67 65 6e 65 74 69 63 |ngs that| genetic|
|00002600| 69 73 74 73 20 6d 69 67 | 68 74 20 77 61 6e 74 0a |ists mig|ht want.|
|00002610| 09 09 74 6f 20 73 65 61 | 72 63 68 20 65 6e 74 69 |..to sea|rch enti|
|00002620| 72 65 20 6c 69 62 72 61 | 72 69 65 73 20 6f 66 20 |re libra|ries of |
|00002630| 39 30 30 30 2d 75 6e 69 | 74 20 6e 75 63 6c 65 6f |9000-uni|t nucleo|
|00002640| 74 69 64 65 20 70 72 6f | 74 65 69 6e 0a 09 09 73 |tide pro|tein...s|
|00002650| 65 71 75 65 6e 63 65 73 | 20 66 6f 72 20 28 28 41 |equences| for ((A|
|00002660| 47 43 41 7c 54 54 47 43 | 41 29 2e 2a 54 47 43 29 |GCA|TTGC|A).*TGC)|
|00002670| 7c 41 47 43 54 29 3f 54 | 3f 41 2b 20 6f 72 20 73 ||AGCT)?T|?A+ or s|
|00002680| 6f 6d 65 20 6e 6f 6e 73 | 65 6e 73 65 0a 09 09 77 |ome nons|ense...w|
|00002690| 68 69 63 68 20 4d 49 47 | 48 54 20 62 65 20 6e 6f |hich MIG|HT be no|
|000026a0| 6e 6c 69 6e 65 61 72 2c | 20 79 6f 75 20 77 6f 75 |nlinear,| you wou|
|000026b0| 6c 64 20 77 61 6e 74 20 | 64 65 6c 74 61 32 2e 20 |ld want |delta2. |
|000026c0| 20 53 6f 20 63 6f 6e 76 | 69 6e 63 65 0a 09 09 73 | So conv|ince...s|
|000026d0| 6f 6d 65 6f 6e 65 20 74 | 6f 20 64 6f 20 74 68 65 |omeone t|o do the|
|000026e0| 20 47 61 6c 69 6c 2f 41 | 70 6f 73 74 6f 6c 69 63 | Galil/A|postolic|
|000026f0| 6f 2f 47 69 61 6e 63 61 | 72 6c 6f 20 32 6e 20 63 |o/Gianca|rlo 2n c|
|00002700| 6f 6d 70 61 72 69 73 6f | 6e 0a 09 09 77 6f 72 73 |ompariso|n...wors|
|00002710| 74 20 63 61 73 65 20 73 | 74 75 66 66 2e 20 20 53 |t case s|tuff. S|
|00002720| 65 65 20 65 67 72 65 70 | 2e 63 20 66 6f 72 20 72 |ee egrep|.c for r|
|00002730| 65 66 65 72 65 6e 63 65 | 2e 0a 09 09 0a 09 47 6f |eference|......Go|
|00002740| 73 70 65 72 2c 20 57 2e | 20 28 48 41 4b 4d 45 4d |sper, W.| (HAKMEM|
|00002750| 20 31 39 37 32 29 3a 0a | 09 09 47 6f 73 70 65 72 | 1972):.|..Gosper|
|00002760| 20 64 69 64 6e 27 74 20 | 67 65 74 20 61 72 6f 75 | didn't |get arou|
|00002770| 6e 64 20 74 6f 20 74 68 | 65 20 54 68 6f 6d 70 73 |nd to th|e Thomps|
|00002780| 6f 6e 2d 6c 69 6b 65 20 | 6d 61 63 68 69 6e 65 20 |on-like |machine |
|00002790| 75 6e 74 69 6c 0a 09 09 | 31 39 37 32 20 77 69 74 |until...|1972 wit|
|000027a0| 68 20 48 41 4b 4d 45 4d | 2e 20 20 48 69 73 20 50 |h HAKMEM|. His P|
|000027b0| 44 50 20 31 30 20 63 6f | 64 65 20 69 73 20 6e 65 |DP 10 co|de is ne|
|000027c0| 76 65 72 74 68 65 6c 65 | 73 73 20 76 61 6c 69 61 |verthele|ss valia|
|000027d0| 6e 74 2e 0a 09 09 48 65 | 20 69 73 20 61 6c 73 6f |nt....He| is also|
|000027e0| 20 28 62 61 72 65 6c 79 | 29 20 63 72 65 64 69 74 | (barely|) credit|
|000027f0| 65 64 20 77 69 74 68 20 | 63 6f 6e 63 65 69 76 69 |ed with |conceivi|
|00002800| 6e 67 20 74 68 65 20 62 | 61 63 6b 77 61 72 64 73 |ng the b|ackwards|
|00002810| 0a 09 09 6d 61 74 63 68 | 20 69 64 65 61 20 69 6e |...match| idea in|
|00002820| 64 65 70 65 6e 64 65 6e | 74 6c 79 2e 20 20 57 68 |dependen|tly. Wh|
|00002830| 65 72 65 20 69 73 20 68 | 65 20 6e 6f 77 3f 0a 09 |ere is h|e now?..|
|00002840| 09 0a 09 4d 6f 72 72 69 | 73 2f 50 72 61 74 74 3a |...Morri|s/Pratt:|
|00002850| 0a 09 09 4e 69 63 65 20 | 67 75 79 73 2c 20 62 75 |...Nice |guys, bu|
|00002860| 74 20 66 6f 72 20 74 68 | 69 73 20 70 75 72 70 6f |t for th|is purpo|
|00002870| 73 65 2c 20 68 61 73 2d | 62 65 65 6e 73 2e 0a 09 |se, has-|beens...|
|00002880| 09 4e 65 61 74 20 74 6f | 20 73 65 65 20 61 20 68 |.Neat to| see a h|
|00002890| 61 63 6b 65 72 27 73 20 | 74 72 69 75 6d 70 68 20 |acker's |triumph |
|000028a0| 62 75 72 79 20 73 6f 6d | 65 20 74 68 65 6f 72 79 |bury som|e theory|
|000028b0| 2e 0a 0a 09 48 6f 72 73 | 70 6f 6f 6c 20 28 53 6f |....Hors|pool (So|
|000028c0| 66 74 77 61 72 65 20 50 | 72 61 63 74 69 63 65 20 |ftware P|ractice |
|000028d0| 26 20 45 78 70 65 72 69 | 65 6e 63 65 2c 20 31 39 |& Experi|ence, 19|
|000028e0| 38 30 29 3a 0a 09 09 4e | 6f 77 20 68 65 72 65 27 |80):...N|ow here'|
|000028f0| 73 20 61 20 43 61 6e 61 | 64 69 61 6e 20 61 66 74 |s a Cana|dian aft|
|00002900| 65 72 20 74 68 65 20 68 | 65 61 72 74 20 6f 66 20 |er the h|eart of |
|00002910| 74 68 69 6e 67 73 0a 09 | 09 28 70 65 72 66 65 63 |things..|.(perfec|
|00002920| 74 20 68 61 73 68 69 6e | 67 2c 20 74 65 78 74 20 |t hashin|g, text |
|00002930| 63 6f 6d 70 72 65 73 73 | 69 6f 6e 2c 20 4e 50 2d |compress|ion, NP-|
|00002940| 63 6f 6d 70 6c 65 74 65 | 0a 09 09 63 6f 64 65 20 |complete|...code |
|00002950| 67 65 6e 65 72 61 74 69 | 6f 6e 20 70 72 6f 62 73 |generati|on probs|
|00002960| 2e 2c 20 65 74 63 2e 29 | 20 20 44 69 64 20 73 6f |., etc.)| Did so|
|00002970| 6d 65 20 41 6d 64 61 68 | 6c 0a 09 09 74 69 6d 69 |me Amdah|l...timi|
|00002980| 6e 67 73 20 74 6f 20 73 | 68 6f 77 20 74 68 61 74 |ngs to s|how that|
|00002990| 20 64 65 6c 74 61 32 20 | 69 73 20 6e 6f 74 20 73 | delta2 |is not s|
|000029a0| 6f 20 68 6f 74 2e 0a 09 | 09 4b 6e 6f 77 73 20 61 |o hot...|.Knows a|
|000029b0| 62 6f 75 74 20 53 65 61 | 72 63 68 20 46 6f 72 20 |bout Sea|rch For |
|000029c0| 4c 65 61 73 74 20 46 72 | 65 71 75 65 6e 74 20 43 |Least Fr|equent C|
|000029d0| 68 61 72 61 63 74 65 72 | 20 46 69 72 73 74 2c 0a |haracter| First,.|
|000029e0| 09 09 77 68 69 63 68 20 | 69 73 20 75 73 65 66 75 |..which |is usefu|
|000029f0| 6c 20 66 6f 72 20 73 68 | 6f 72 74 20 70 61 74 74 |l for sh|ort patt|
|00002a00| 65 72 6e 73 2e 20 0a 0a | 09 7b 2c 65 2c 66 7d 67 |erns. ..|.{,e,f}g|
|00002a10| 72 65 70 20 6d 61 6e 20 | 70 61 67 65 3a 0a 09 09 |rep man |page:...|
|00002a20| 54 68 65 20 6c 61 75 67 | 68 61 62 6c 65 20 62 75 |The laug|hable bu|
|00002a30| 67 6e 6f 74 65 20 22 62 | 75 74 20 77 65 20 64 6f |gnote "b|ut we do|
|00002a40| 20 6e 6f 74 20 6b 6e 6f | 77 20 61 20 73 69 6e 67 | not kno|w a sing|
|00002a50| 6c 65 20 61 6c 67 6f 72 | 69 74 68 6d 0a 09 09 74 |le algor|ithm...t|
|00002a60| 68 61 74 20 73 70 61 6e | 73 20 61 20 77 69 64 65 |hat span|s a wide|
|00002a70| 20 65 6e 6f 75 67 68 20 | 72 61 6e 67 65 20 6f 66 | enough |range of|
|00002a80| 20 73 70 61 63 65 2d 74 | 69 6d 65 20 74 72 61 64 | space-t|ime trad|
|00002a90| 65 6f 66 66 73 22 0a 09 | 09 63 65 72 74 61 69 6e |eoffs"..|.certain|
|00002aa0| 6c 79 20 70 72 65 73 75 | 6d 65 73 20 74 68 61 74 |ly presu|mes that|
|00002ab0| 20 74 68 65 72 65 20 69 | 73 20 6e 6f 20 73 75 63 | there i|s no suc|
|00002ac0| 68 20 74 68 69 6e 67 20 | 61 73 20 73 77 69 74 63 |h thing |as switc|
|00002ad0| 68 69 6e 67 0a 09 09 6c | 6f 67 69 63 2e 20 20 48 |hing...l|ogic. H|
|00002ae0| 6f 77 20 74 68 65 20 27 | 67 72 65 70 27 20 66 61 |ow the '|grep' fa|
|00002af0| 6d 69 6c 79 20 67 6f 74 | 20 69 6e 74 6f 20 61 20 |mily got| into a |
|00002b00| 6d 75 6c 74 69 70 6c 65 | 2d 76 65 72 73 69 6f 6e |multiple|-version|
|00002b10| 0a 09 09 6d 65 73 73 20 | 69 73 20 70 72 6f 62 61 |...mess |is proba|
|00002b20| 62 6c 79 20 61 20 47 75 | 79 20 48 61 72 72 69 73 |bly a Gu|y Harris|
|00002b30| 20 73 74 6f 72 79 3b 20 | 27 65 67 72 65 70 27 20 | story; |'egrep' |
|00002b40| 6c 6f 6f 6b 73 20 6c 69 | 6b 65 20 74 68 65 0a 09 |looks li|ke the..|
|00002b50| 09 77 69 6e 6e 65 72 2c | 20 61 73 20 69 74 73 20 |.winner,| as its |
|00002b60| 66 75 6e 63 74 69 6f 6e | 61 6c 69 74 79 20 69 73 |function|ality is|
|00002b70| 20 70 72 65 74 74 79 20 | 6d 75 63 68 20 61 20 73 | pretty |much a s|
|00002b80| 75 70 65 72 73 65 74 20 | 6f 66 0a 09 09 74 68 65 |uperset |of...the|
|00002b90| 20 6f 74 68 65 72 20 74 | 77 6f 2e 20 20 54 68 65 | other t|wo. The|
|00002ba0| 20 4b 20 26 20 50 20 74 | 65 61 73 65 72 20 28 70 | K & P t|easer (p|
|00002bb0| 2e 20 31 30 35 29 20 6f | 66 66 65 72 73 20 68 6f |. 105) o|ffers ho|
|00002bc0| 70 65 20 66 6f 72 0a 09 | 09 75 6e 69 66 69 63 61 |pe for..|.unifica|
|00002bd0| 74 69 6f 6e 2c 20 62 75 | 74 20 77 65 20 73 65 65 |tion, bu|t we see|
|00002be0| 20 6e 6f 20 64 69 66 66 | 65 72 65 6e 63 65 20 77 | no diff|erence w|
|00002bf0| 69 74 68 20 65 78 74 61 | 6e 74 20 56 38 20 63 6f |ith exta|nt V8 co|
|00002c00| 64 65 2e 0a 0a 20 20 20 | 20 20 22 4e 6f 74 20 63 |de... | "Not c|
|00002c10| 69 74 65 64 20 69 6e 20 | 74 68 65 20 74 65 78 74 |ited in |the text|
|00002c20| 22 20 2d 2d 20 74 68 65 | 20 73 65 78 79 20 72 61 |" -- the| sexy ra|
|00002c30| 6e 64 6f 6d 69 7a 65 64 | 20 4b 61 72 70 2f 52 61 |ndomized| Karp/Ra|
|00002c40| 62 69 6e 20 73 74 72 69 | 6e 67 20 73 65 61 72 63 |bin stri|ng searc|
|00002c50| 68 65 72 0a 28 53 65 64 | 67 65 77 69 63 6b 2c 20 |her.(Sed|gewick, |
|00002c60| 41 6c 67 6f 72 69 74 68 | 6d 73 2c 20 6f 72 20 4b |Algorith|ms, or K|
|00002c70| 61 72 70 27 73 20 54 75 | 72 69 6e 67 20 41 77 61 |arp's Tu|ring Awa|
|00002c80| 72 64 20 4c 65 63 74 75 | 72 65 29 2c 20 61 6e 64 |rd Lectu|re), and|
|00002c90| 20 74 68 65 20 72 69 62 | 61 6c 64 20 63 6c 61 73 | the rib|ald clas|
|00002ca0| 73 69 63 0a 54 69 6d 65 | 20 57 61 72 70 73 2c 20 |sic.Time| Warps, |
|00002cb0| 53 74 72 69 6e 67 20 45 | 64 69 74 73 2c 20 61 6e |String E|dits, an|
|00002cc0| 64 20 4d 61 63 72 6f 6d | 6f 6c 65 63 75 6c 65 73 |d Macrom|olecules|
|00002cd0| 20 2d 2d 20 54 68 65 20 | 54 68 65 6f 72 79 20 61 | -- The |Theory a|
|00002ce0| 6e 64 20 50 72 61 63 74 | 69 63 65 0a 6f 66 20 53 |nd Pract|ice.of S|
|00002cf0| 65 71 75 65 6e 63 65 20 | 43 6f 6d 70 61 72 69 73 |equence |Comparis|
|00002d00| 6f 6e 20 28 4b 72 75 73 | 6b 61 6c 20 26 20 53 61 |on (Krus|kal & Sa|
|00002d10| 6e 6b 6f 66 66 29 2e 20 | 20 49 6e 71 75 69 72 65 |nkoff). | Inquire|
|00002d20| 20 77 69 74 68 69 6e 2e | 0a 54 68 61 6e 6b 73 20 | within.|.Thanks |
|00002d30| 66 6f 72 20 79 6f 75 72 | 20 70 61 74 69 65 6e 63 |for your| patienc|
|00002d40| 65 2c 0a 0a 20 20 20 20 | 20 4a 61 6d 65 73 20 41 |e,.. | James A|
|00002d50| 2e 20 57 6f 6f 64 73 20 | 28 61 6d 65 73 21 6a 61 |. Woods |(ames!ja|
|00002d60| 77 29 0a 20 20 20 20 20 | 4e 41 53 41 20 41 6d 65 |w). |NASA Ame|
|00002d70| 73 20 52 65 73 65 61 72 | 63 68 20 43 65 6e 74 65 |s Resear|ch Cente|
|00002d80| 72 0a 0a 50 2e 53 2e 0a | 20 20 20 20 20 43 75 72 |r..P.S..| Cur|
|00002d90| 72 65 6e 74 20 61 70 70 | 6c 69 63 61 74 69 6f 6e |rent app|lication|
|00002da0| 73 20 66 6f 72 20 42 6f | 79 65 72 2d 4d 6f 6f 72 |s for Bo|yer-Moor|
|00002db0| 65 20 63 6f 64 65 20 69 | 6e 63 6c 75 64 65 20 6d |e code i|nclude m|
|00002dc0| 6f 64 69 66 69 63 61 74 | 69 6f 6e 20 6f 66 20 0a |odificat|ion of .|
|00002dd0| 27 66 61 73 74 66 69 6e | 64 27 20 66 6f 72 20 74 |'fastfin|d' for t|
|00002de0| 72 75 65 20 73 70 65 65 | 64 2c 20 61 73 20 77 65 |rue spee|d, as we|
|00002df0| 6c 6c 20 61 73 20 73 75 | 62 73 74 72 69 6e 67 20 |ll as su|bstring |
|00002e00| 73 65 61 72 63 68 20 66 | 6f 72 20 27 67 72 61 62 |search f|or 'grab|
|00002e10| 27 2c 20 62 6f 74 68 0a | 62 65 6e 65 66 69 74 69 |', both.|benefiti|
|00002e20| 6e 67 20 66 72 6f 6d 20 | 42 4d 2d 73 74 79 6c 65 |ng from |BM-style|
|00002e30| 20 73 65 61 72 63 68 20 | 74 68 72 75 20 69 6e 63 | search |thru inc|
|00002e40| 72 65 6d 65 6e 74 61 6c | 6c 79 2d 63 6f 6d 70 72 |remental|ly-compr|
|00002e50| 65 73 73 65 64 20 66 69 | 6c 65 73 2f 69 6e 64 69 |essed fi|les/indi|
|00002e60| 63 65 73 2e 0a 0a 53 48 | 41 52 5f 45 4f 46 0a 69 |ces...SH|AR_EOF.i|
|00002e70| 66 20 74 65 73 74 20 34 | 36 32 33 20 2d 6e 65 20 |f test 4|623 -ne |
|00002e80| 22 60 77 63 20 2d 63 20 | 3c 20 27 70 65 70 34 67 |"`wc -c |< 'pep4g|
|00002e90| 72 65 70 2e 32 27 60 22 | 0a 74 68 65 6e 0a 09 65 |rep.2'`"|.then..e|
|00002ea0| 63 68 6f 20 73 68 61 72 | 3a 20 65 72 72 6f 72 20 |cho shar|: error |
|00002eb0| 74 72 61 6e 73 6d 69 74 | 74 69 6e 67 20 22 27 70 |transmit|ting "'p|
|00002ec0| 65 70 34 67 72 65 70 2e | 32 27 22 20 27 28 73 68 |ep4grep.|2'" '(sh|
|00002ed0| 6f 75 6c 64 20 68 61 76 | 65 20 62 65 65 6e 20 34 |ould hav|e been 4|
|00002ee0| 36 32 33 20 63 68 61 72 | 61 63 74 65 72 73 29 27 |623 char|acters)'|
|00002ef0| 0a 66 69 0a 66 69 0a 65 | 63 68 6f 20 73 68 61 72 |.fi.fi.e|cho shar|
|00002f00| 3a 20 65 78 74 72 61 63 | 74 69 6e 67 20 22 27 4d |: extrac|ting "'M|
|00002f10| 61 6b 65 66 69 6c 65 27 | 22 20 27 28 35 39 33 20 |akefile'|" '(593 |
|00002f20| 63 68 61 72 61 63 74 65 | 72 73 29 27 0a 69 66 20 |characte|rs)'.if |
|00002f30| 74 65 73 74 20 2d 66 20 | 27 4d 61 6b 65 66 69 6c |test -f |'Makefil|
|00002f40| 65 27 0a 74 68 65 6e 0a | 09 65 63 68 6f 20 73 68 |e'.then.|.echo sh|
|00002f50| 61 72 3a 20 77 69 6c 6c | 20 6e 6f 74 20 6f 76 65 |ar: will| not ove|
|00002f60| 72 2d 77 72 69 74 65 20 | 65 78 69 73 74 69 6e 67 |r-write |existing|
|00002f70| 20 66 69 6c 65 20 22 27 | 4d 61 6b 65 66 69 6c 65 | file "'|Makefile|
|00002f80| 27 22 0a 65 6c 73 65 0a | 63 61 74 20 3c 3c 20 5c |'".else.|cat << \|
|00002f90| 53 48 41 52 5f 45 4f 46 | 20 3e 20 27 4d 61 6b 65 |SHAR_EOF| > 'Make|
|00002fa0| 66 69 6c 65 27 0a 23 20 | 6f 70 74 69 6f 6e 61 6c |file'.# |optional|
|00002fb0| 20 69 74 65 6d 73 20 66 | 6f 72 20 45 4e 56 3a 0a | items f|or ENV:.|
|00002fc0| 23 20 2d 44 42 53 44 09 | 09 09 6d 61 6b 65 20 2d |# -DBSD.|..make -|
|00002fd0| 69 20 77 6f 72 6b 20 61 | 73 20 69 6e 20 53 79 73 |i work a|s in Sys|
|00002fe0| 74 65 6d 20 56 0a 23 20 | 2d 49 2e 09 09 09 75 73 |tem V.# |-I....us|
|00002ff0| 65 20 72 65 67 65 78 70 | 2e 68 20 69 6e 20 63 75 |e regexp|.h in cu|
|00003000| 72 72 65 6e 74 20 64 69 | 72 65 63 74 6f 72 79 2c |rrent di|rectory,|
|00003010| 20 6e 6f 74 20 2f 75 73 | 72 2f 69 6e 63 6c 75 64 | not /us|r/includ|
|00003020| 65 0a 23 20 2d 44 45 47 | 52 45 50 3d 70 61 74 68 |e.# -DEG|REP=path|
|00003030| 09 09 64 65 66 61 75 6c | 74 20 2f 75 73 72 2f 62 |..defaul|t /usr/b|
|00003040| 69 6e 2f 65 67 72 65 70 | 0a 23 20 2d 44 56 37 09 |in/egrep|.# -DV7.|
|00003050| 09 09 69 6e 76 6f 6b 65 | 20 78 72 65 61 64 28 29 |..invoke| xread()|
|00003060| 20 66 6f 72 20 73 79 73 | 74 65 6d 20 74 69 6d 65 | for sys|tem time|
|00003070| 20 71 75 69 72 6b 0a 0a | 45 4e 56 3d 20 2d 49 2e | quirk..|ENV= -I.|
|00003080| 20 2d 44 42 53 44 0a 0a | 23 20 6f 70 74 69 6f 6e | -DBSD..|# option|
|00003090| 61 6c 20 69 74 65 6d 73 | 20 66 6f 72 20 4f 42 4a |al items| for OBJ|
|000030a0| 3a 0a 23 20 63 6f 6d 70 | 61 74 2d 73 79 73 35 2e |:.# comp|at-sys5.|
|000030b0| 6f 09 09 66 6f 72 20 56 | 37 20 6f 72 20 42 53 44 |o..for V|7 or BSD|
|000030c0| 20 34 2e 32 20 73 79 73 | 74 65 6d 73 20 77 2f 6e | 4.2 sys|tems w/n|
|000030d0| 6f 20 67 65 74 6f 70 74 | 28 33 29 20 6f 72 20 73 |o getopt|(3) or s|
|000030e0| 74 72 69 6e 67 28 33 29 | 0a 23 20 72 65 67 65 78 |tring(3)|.# regex|
|000030f0| 70 2e 6f 09 09 69 66 20 | 48 65 6e 72 79 20 53 70 |p.o..if |Henry Sp|
|00003100| 65 6e 63 65 72 27 73 20 | 72 65 67 65 78 70 28 33 |encer's |regexp(3|
|00003110| 29 20 69 73 20 6e 6f 74 | 20 69 6e 73 74 61 6c 6c |) is not| install|
|00003120| 65 64 0a 23 20 72 65 67 | 65 72 72 6f 72 2e 6f 09 |ed.# reg|error.o.|
|00003130| 09 09 22 0a 23 09 09 09 | 56 38 20 70 65 6f 70 6c |..".#...|V8 peopl|
|00003140| 65 20 2d 2d 20 79 6f 75 | 72 20 72 65 67 65 78 70 |e -- you|r regexp|
|00003150| 2e 68 20 77 6f 6e 27 74 | 20 64 6f 0a 0a 4f 42 4a |.h won't| do..OBJ|
|00003160| 3d 20 72 65 67 65 78 70 | 2e 6f 20 72 65 67 65 72 |= regexp|.o reger|
|00003170| 72 6f 72 2e 6f 20 63 6f | 6d 70 61 74 2d 73 79 73 |ror.o co|mpat-sys|
|00003180| 35 2e 6f 0a 0a 43 46 4c | 41 47 53 3d 20 2d 4f 20 |5.o..CFL|AGS= -O |
|00003190| 2d 69 20 24 28 45 4e 56 | 29 20 0a 0a 65 67 72 65 |-i $(ENV|) ..egre|
|000031a0| 70 3a 09 65 67 72 65 70 | 2e 6f 20 24 28 4f 42 4a |p:.egrep|.o $(OBJ|
|000031b0| 29 0a 09 63 63 20 24 28 | 43 46 4c 41 47 53 29 20 |)..cc $(|CFLAGS) |
|000031c0| 24 28 4f 42 4a 29 20 65 | 67 72 65 70 2e 6f 20 2d |$(OBJ) e|grep.o -|
|000031d0| 6f 20 65 67 72 65 70 0a | 0a 69 6e 73 74 61 6c 6c |o egrep.|.install|
|000031e0| 3a 0a 09 6d 76 20 65 67 | 72 65 70 20 2f 75 73 72 |:..mv eg|rep /usr|
|000031f0| 2f 6c 6f 63 61 6c 0a 53 | 48 41 52 5f 45 4f 46 0a |/local.S|HAR_EOF.|
|00003200| 69 66 20 74 65 73 74 20 | 35 39 33 20 2d 6e 65 20 |if test |593 -ne |
|00003210| 22 60 77 63 20 2d 63 20 | 3c 20 27 4d 61 6b 65 66 |"`wc -c |< 'Makef|
|00003220| 69 6c 65 27 60 22 0a 74 | 68 65 6e 0a 09 65 63 68 |ile'`".t|hen..ech|
|00003230| 6f 20 73 68 61 72 3a 20 | 65 72 72 6f 72 20 74 72 |o shar: |error tr|
|00003240| 61 6e 73 6d 69 74 74 69 | 6e 67 20 22 27 4d 61 6b |ansmitti|ng "'Mak|
|00003250| 65 66 69 6c 65 27 22 20 | 27 28 73 68 6f 75 6c 64 |efile'" |'(should|
|00003260| 20 68 61 76 65 20 62 65 | 65 6e 20 35 39 33 20 63 | have be|en 593 c|
|00003270| 68 61 72 61 63 74 65 72 | 73 29 27 0a 66 69 0a 66 |haracter|s)'.fi.f|
|00003280| 69 0a 65 63 68 6f 20 73 | 68 61 72 3a 20 65 78 74 |i.echo s|har: ext|
|00003290| 72 61 63 74 69 6e 67 20 | 22 27 65 67 72 65 70 2e |racting |"'egrep.|
|000032a0| 63 27 22 20 27 28 31 31 | 32 31 39 20 63 68 61 72 |c'" '(11|219 char|
|000032b0| 61 63 74 65 72 73 29 27 | 0a 69 66 20 74 65 73 74 |acters)'|.if test|
|000032c0| 20 2d 66 20 27 65 67 72 | 65 70 2e 63 27 0a 74 68 | -f 'egr|ep.c'.th|
|000032d0| 65 6e 0a 09 65 63 68 6f | 20 73 68 61 72 3a 20 77 |en..echo| shar: w|
|000032e0| 69 6c 6c 20 6e 6f 74 20 | 6f 76 65 72 2d 77 72 69 |ill not |over-wri|
|000032f0| 74 65 20 65 78 69 73 74 | 69 6e 67 20 66 69 6c 65 |te exist|ing file|
|00003300| 20 22 27 65 67 72 65 70 | 2e 63 27 22 0a 65 6c 73 | "'egrep|.c'".els|
|00003310| 65 0a 63 61 74 20 3c 3c | 20 5c 53 48 41 52 5f 45 |e.cat <<| \SHAR_E|
|00003320| 4f 46 20 3e 20 27 65 67 | 72 65 70 2e 63 27 0a 2f |OF > 'eg|rep.c'./|
|00003330| 2a 0a 20 20 20 20 20 42 | 6f 79 65 72 2f 4d 6f 6f |*. B|oyer/Moo|
|00003340| 72 65 2f 47 6f 73 70 65 | 72 2d 61 73 73 69 73 74 |re/Gospe|r-assist|
|00003350| 65 64 20 27 65 67 72 65 | 70 27 20 73 65 61 72 63 |ed 'egre|p' searc|
|00003360| 68 2c 20 77 69 74 68 20 | 64 65 6c 74 61 30 20 74 |h, with |delta0 t|
|00003370| 61 62 6c 65 20 61 73 20 | 69 6e 0a 20 20 20 20 20 |able as |in. |
|00003380| 6f 72 69 67 69 6e 61 6c | 20 70 61 70 65 72 20 28 |original| paper (|
|00003390| 43 41 43 4d 2c 20 4f 63 | 74 6f 62 65 72 2c 20 31 |CACM, Oc|tober, 1|
|000033a0| 39 37 37 29 2e 20 20 4e | 6f 20 64 65 6c 74 61 31 |977). N|o delta1|
|000033b0| 20 6f 72 20 64 65 6c 74 | 61 32 2e 20 20 41 63 63 | or delt|a2. Acc|
|000033c0| 6f 72 64 69 6e 67 20 74 | 6f 0a 20 20 20 20 20 65 |ording t|o. e|
|000033d0| 78 70 65 72 69 6d 65 6e | 74 20 28 48 6f 72 73 70 |xperimen|t (Horsp|
|000033e0| 6f 6f 6c 2c 20 53 6f 66 | 74 2e 20 50 72 61 63 2e |ool, Sof|t. Prac.|
|000033f0| 20 45 78 70 2e 2c 20 31 | 39 38 32 29 2c 20 64 65 | Exp., 1|982), de|
|00003400| 6c 74 61 32 20 69 73 20 | 6f 66 20 6d 69 6e 69 6d |lta2 is |of minim|
|00003410| 61 6c 0a 20 20 20 20 20 | 70 72 61 63 74 69 63 61 |al. |practica|
|00003420| 6c 20 76 61 6c 75 65 2e | 20 20 48 6f 77 65 76 65 |l value.| Howeve|
|00003430| 72 2c 20 74 6f 20 69 6d | 70 72 6f 76 65 20 66 6f |r, to im|prove fo|
|00003440| 72 20 77 6f 72 73 74 20 | 63 61 73 65 20 69 6e 70 |r worst |case inp|
|00003450| 75 74 2c 20 69 6e 74 65 | 67 72 61 74 69 6e 67 0a |ut, inte|grating.|
|00003460| 20 20 20 20 20 74 68 65 | 20 69 6d 70 72 6f 76 65 | the| improve|
|00003470| 64 20 47 61 6c 69 6c 20 | 73 74 72 61 74 65 67 69 |d Galil |strategi|
|00003480| 65 73 20 28 41 70 6f 73 | 74 6f 6c 69 63 6f 2f 47 |es (Apos|tolico/G|
|00003490| 69 61 6e 63 61 72 6c 6f | 2c 20 53 69 61 6d 2e 20 |iancarlo|, Siam. |
|000034a0| 4a 2e 20 43 6f 6d 70 75 | 74 2e 2c 0a 20 20 20 20 |J. Compu|t.,. |
|000034b0| 20 46 65 62 72 75 61 72 | 79 20 31 39 38 36 29 20 | Februar|y 1986) |
|000034c0| 64 65 73 65 72 76 65 73 | 20 63 6f 6e 73 69 64 65 |deserves| conside|
|000034d0| 72 61 74 69 6f 6e 2e 0a | 0a 20 20 20 20 20 4d 65 |ration..|. Me|
|000034e0| 74 68 6f 64 3a 20 09 65 | 78 74 72 61 63 74 20 6c |thod: .e|xtract l|
|000034f0| 6f 6e 67 65 73 74 20 6d | 65 74 61 63 68 61 72 61 |ongest m|etachara|
|00003500| 63 74 65 72 2d 66 72 65 | 65 20 73 74 72 69 6e 67 |cter-fre|e string|
|00003510| 20 66 72 6f 6d 20 65 78 | 70 72 65 73 73 69 6f 6e | from ex|pression|
|00003520| 2e 0a 09 09 74 68 69 73 | 20 69 73 20 64 6f 6e 65 |....this| is done|
|00003530| 20 75 73 69 6e 67 20 61 | 20 73 69 64 65 2d 65 66 | using a| side-ef|
|00003540| 66 65 63 74 20 66 72 6f | 6d 20 68 65 6e 72 79 20 |fect fro|m henry |
|00003550| 73 70 65 6e 63 65 72 27 | 73 20 72 65 67 63 6f 6d |spencer'|s regcom|
|00003560| 70 28 29 2e 0a 09 09 75 | 73 65 20 62 6f 79 65 72 |p()....u|se boyer|
|00003570| 2d 6d 6f 6f 72 65 20 74 | 6f 20 6d 61 74 63 68 20 |-moore t|o match |
|00003580| 73 75 63 68 2c 20 74 68 | 65 6e 20 70 61 73 73 20 |such, th|en pass |
|00003590| 73 75 62 6d 61 74 63 68 | 69 6e 67 20 6c 69 6e 65 |submatch|ing line|
|000035a0| 73 0a 09 09 74 6f 20 72 | 65 78 65 78 70 28 29 20 |s...to r|exexp() |
|000035b0| 66 6f 72 20 73 68 6f 72 | 74 20 69 6e 70 75 74 2c |for shor|t input,|
|000035c0| 20 6f 72 20 73 74 61 6e | 64 61 72 64 20 27 65 67 | or stan|dard 'eg|
|000035d0| 72 65 70 27 20 66 6f 72 | 20 6c 6f 6e 67 0a 09 09 |rep' for| long...|
|000035e0| 69 6e 70 75 74 2e 20 20 | 28 74 68 69 73 20 74 72 |input. |(this tr|
|000035f0| 61 64 65 6f 66 66 20 69 | 73 20 64 75 65 20 74 6f |adeoff i|s due to|
|00003600| 20 74 68 65 20 67 65 6e | 65 72 61 6c 20 73 6c 6f | the gen|eral slo|
|00003610| 77 6e 65 73 73 20 6f 66 | 20 74 68 65 0a 09 09 72 |wness of| the...r|
|00003620| 65 67 65 78 70 28 29 20 | 6e 6f 6e 64 65 74 65 72 |egexp() |nondeter|
|00003630| 6d 69 6e 69 73 74 69 63 | 20 6d 61 63 68 69 6e 65 |ministic| machine|
|00003640| 20 6f 6e 20 63 6f 6d 70 | 6c 65 78 20 65 78 70 72 | on comp|lex expr|
|00003650| 65 73 73 69 6f 6e 73 2c | 0a 09 09 61 73 20 77 65 |essions,|...as we|
|00003660| 6c 6c 20 61 73 20 74 68 | 65 20 73 74 61 72 74 75 |ll as th|e startu|
|00003670| 70 20 74 69 6d 65 20 6f | 66 20 27 65 67 72 65 70 |p time o|f 'egrep|
|00003680| 27 20 6f 6e 20 73 68 6f | 72 74 20 66 69 6c 65 73 |' on sho|rt files|
|00003690| 2e 29 0a 09 09 61 6c 74 | 65 72 6e 61 74 69 76 65 |.)...alt|ernative|
|000036a0| 6c 79 2c 20 79 6f 75 20 | 6d 61 79 20 63 68 61 6e |ly, you |may chan|
|000036b0| 67 65 20 74 68 65 20 66 | 61 73 74 65 72 20 27 65 |ge the f|aster 'e|
|000036c0| 67 72 65 70 27 20 61 75 | 74 6f 6d 61 74 6f 6e 0a |grep' au|tomaton.|
|000036d0| 09 09 74 6f 20 69 6e 63 | 6c 75 64 65 20 62 6f 79 |..to inc|lude boy|
|000036e0| 65 72 2d 6d 6f 6f 72 65 | 20 64 69 72 65 63 74 6c |er-moore| directl|
|000036f0| 79 2e 0a 20 20 20 20 20 | 46 75 74 75 72 65 3a 20 |y.. |Future: |
|00003700| 0a 20 20 20 20 20 09 09 | 62 65 65 66 20 75 70 20 |. ..|beef up |
|00003710| 66 6f 72 20 6d 75 6c 74 | 69 70 6c 65 20 70 61 74 |for mult|iple pat|
|00003720| 74 65 72 6e 73 20 61 6c | 61 20 62 6d 2f 66 67 72 |terns al|a bm/fgr|
|00003730| 65 70 2e 20 20 63 61 6e | 20 64 6f 20 66 61 73 74 |ep. can| do fast|
|00003740| 20 2d 6e 20 0a 09 09 76 | 69 61 20 66 69 6c 65 20 | -n ...v|ia file |
|00003750| 72 65 73 63 61 6e 2c 20 | 62 75 74 20 69 74 27 73 |rescan, |but it's|
|00003760| 20 61 20 6c 75 78 75 72 | 79 2e 20 20 61 64 61 70 | a luxur|y. adap|
|00003770| 74 20 27 66 61 73 74 66 | 69 6e 64 27 2e 0a 09 09 |t 'fastf|ind'....|
|00003780| 69 6e 74 65 72 6e 61 74 | 69 6f 6e 61 6c 69 7a 65 |internat|ionalize|
|00003790| 20 66 6f 72 20 6b 61 6e | 6a 69 2e 0a 0a 20 20 20 | for kan|ji... |
|000037a0| 20 20 4a 61 6d 65 73 20 | 41 2e 20 57 6f 6f 64 73 | James |A. Woods|
|000037b0| 09 09 09 09 09 43 6f 70 | 79 72 69 67 68 74 20 28 |.....Cop|yright (|
|000037c0| 63 29 20 31 39 38 36 0a | 20 20 20 20 20 4e 41 53 |c) 1986.| NAS|
|000037d0| 41 20 41 6d 65 73 20 52 | 65 73 65 61 72 63 68 20 |A Ames R|esearch |
|000037e0| 43 65 6e 74 65 72 0a 2a | 2f 0a 23 69 66 64 65 66 |Center.*|/.#ifdef|
|000037f0| 09 56 37 0a 23 64 65 66 | 69 6e 65 20 42 53 44 0a |.V7.#def|ine BSD.|
|00003800| 23 64 65 66 69 6e 65 20 | 76 6f 69 64 09 69 6e 74 |#define |void.int|
|00003810| 0a 23 65 6e 64 69 66 0a | 0a 23 69 6e 63 6c 75 64 |.#endif.|.#includ|
|00003820| 65 20 3c 73 74 64 69 6f | 2e 68 3e 0a 23 69 6e 63 |e <stdio|.h>.#inc|
|00003830| 6c 75 64 65 20 3c 63 74 | 79 70 65 2e 68 3e 0a 23 |lude <ct|ype.h>.#|
|00003840| 69 6e 63 6c 75 64 65 20 | 3c 73 79 73 2f 74 79 70 |include |<sys/typ|
|00003850| 65 73 2e 68 3e 0a 23 69 | 6e 63 6c 75 64 65 20 3c |es.h>.#i|nclude <|
|00003860| 73 79 73 2f 73 74 61 74 | 2e 68 3e 0a 23 69 6e 63 |sys/stat|.h>.#inc|
|00003870| 6c 75 64 65 20 3c 72 65 | 67 65 78 70 2e 68 3e 09 |lude <re|gexp.h>.|
|00003880| 09 2f 2a 20 6d 75 73 74 | 20 62 65 20 68 65 6e 72 |./* must| be henr|
|00003890| 79 20 73 70 65 6e 63 65 | 72 27 73 20 76 65 72 73 |y spence|r's vers|
|000038a0| 69 6f 6e 20 2a 2f 0a 0a | 23 69 66 64 65 66 09 42 |ion */..|#ifdef.B|
|000038b0| 53 44 0a 23 64 65 66 69 | 6e 65 09 73 74 72 63 68 |SD.#defi|ne.strch|
|000038c0| 72 09 69 6e 64 65 78 0a | 23 65 6e 64 69 66 0a 23 |r.index.|#endif.#|
|000038d0| 69 66 6e 64 65 66 20 45 | 47 52 45 50 0a 23 64 65 |ifndef E|GREP.#de|
|000038e0| 66 69 6e 65 09 45 47 52 | 45 50 09 22 2f 75 73 72 |fine.EGR|EP."/usr|
|000038f0| 2f 62 69 6e 2f 65 67 72 | 65 70 22 20 20 2f 2a 20 |/bin/egr|ep" /* |
|00003900| 70 72 65 76 65 6e 74 20 | 69 6e 73 74 61 6c 6c 61 |prevent |installa|
|00003910| 74 69 6f 6e 2d 64 65 70 | 65 6e 64 65 6e 74 20 72 |tion-dep|endent r|
|00003920| 65 63 75 72 73 69 6f 6e | 20 2a 2f 0a 23 65 6e 64 |ecursion| */.#end|
|00003930| 69 66 0a 23 64 65 66 69 | 6e 65 20 42 55 46 53 49 |if.#defi|ne BUFSI|
|00003940| 5a 45 09 38 31 39 32 0a | 23 64 65 66 69 6e 65 20 |ZE.8192.|#define |
|00003950| 50 41 54 53 49 5a 45 20 | 31 30 30 30 0a 23 64 65 |PATSIZE |1000.#de|
|00003960| 66 69 6e 65 20 4c 41 52 | 47 45 20 09 42 55 46 53 |fine LAR|GE .BUFS|
|00003970| 49 5a 45 20 2b 20 50 41 | 54 53 49 5a 45 0a 23 64 |IZE + PA|TSIZE.#d|
|00003980| 65 66 69 6e 65 20 46 53 | 49 5a 45 09 35 30 30 30 |efine FS|IZE.5000|
|00003990| 30 09 09 2f 2a 20 61 6c | 67 6f 72 69 74 68 6d 20 |0../* al|gorithm |
|000039a0| 74 72 61 64 65 6f 66 66 | 20 61 74 20 74 68 69 73 |tradeoff| at this|
|000039b0| 20 6c 65 6e 67 74 68 20 | 28 61 64 20 68 6f 63 29 | length |(ad hoc)|
|000039c0| 20 2a 2f 0a 23 64 65 66 | 69 6e 65 20 4e 4c 09 27 | */.#def|ine NL.'|
|000039d0| 5c 6e 27 0a 23 64 65 66 | 69 6e 65 09 45 4f 53 09 |\n'.#def|ine.EOS.|
|000039e0| 27 5c 30 27 0a 0a 65 78 | 74 65 72 6e 20 63 68 61 |'\0'..ex|tern cha|
|000039f0| 72 20 2a 6f 70 74 61 72 | 67 3b 0a 65 78 74 65 72 |r *optar|g;.exter|
|00003a00| 6e 20 69 6e 74 20 6f 70 | 74 69 6e 64 3b 0a 0a 69 |n int op|tind;..i|
|00003a10| 6e 74 20 63 66 6c 61 67 | 2c 20 69 66 6c 61 67 2c |nt cflag|, iflag,|
|00003a20| 20 65 66 6c 61 67 2c 20 | 66 66 6c 61 67 2c 20 6c | eflag, |fflag, l|
|00003a30| 66 6c 61 67 3b 0a 69 6e | 74 20 62 6f 79 66 6c 61 |flag;.in|t boyfla|
|00003a40| 67 2c 20 72 78 66 6c 61 | 67 3b 0a 69 6e 74 20 68 |g, rxfla|g;.int h|
|00003a50| 66 6c 61 67 3b 0a 69 6e | 74 20 6e 66 69 6c 65 2c |flag;.in|t nfile,|
|00003a60| 20 6e 73 75 63 63 65 73 | 73 3b 0a 6c 6f 6e 67 20 | nsucces|s;.long |
|00003a70| 6e 6d 61 74 63 68 3b 0a | 0a 72 65 67 65 78 70 20 |nmatch;.|.regexp |
|00003a80| 2a 72 73 70 65 6e 63 65 | 72 3b 0a 63 68 61 72 20 |*rspence|r;.char |
|00003a90| 2a 70 61 74 74 65 72 6e | 2c 20 2a 70 61 74 62 6f |*pattern|, *patbo|
|00003aa0| 79 3b 0a 69 6e 74 20 64 | 65 6c 74 61 30 5b 32 35 |y;.int d|elta0[25|
|00003ab0| 36 5d 3b 09 09 2f 2a 20 | 61 73 63 69 69 20 6f 6e |6];../* |ascii on|
|00003ac0| 6c 79 20 2d 2d 20 73 65 | 65 20 6e 6f 74 65 20 61 |ly -- se|e note a|
|00003ad0| 74 20 67 6f 73 70 65 72 | 28 29 20 2a 2f 0a 63 68 |t gosper|() */.ch|
|00003ae0| 61 72 20 63 6d 61 70 5b | 32 35 36 5d 3b 09 09 09 |ar cmap[|256];...|
|00003af0| 2f 2a 20 28 75 6e 29 66 | 6f 6c 64 65 64 20 63 68 |/* (un)f|olded ch|
|00003b00| 61 72 61 63 74 65 72 73 | 20 2a 2f 0a 63 68 61 72 |aracters| */.char|
|00003b10| 20 73 74 72 5b 42 55 46 | 53 49 5a 45 2b 32 5d 3b | str[BUF|SIZE+2];|
|00003b20| 0a 63 68 61 72 20 6c 69 | 6e 65 74 65 6d 70 5b 42 |.char li|netemp[B|
|00003b30| 55 46 53 49 5a 45 5d 3b | 0a 63 68 61 72 20 67 72 |UFSIZE];|.char gr|
|00003b40| 65 70 63 6d 64 5b 50 41 | 54 53 49 5a 45 5d 3b 20 |epcmd[PA|TSIZE]; |
|00003b50| 0a 0a 73 74 72 75 63 74 | 20 73 74 61 74 20 73 74 |..struct| stat st|
|00003b60| 62 75 66 3b 0a 69 6e 74 | 20 66 64 3b 0a 46 49 4c |buf;.int| fd;.FIL|
|00003b70| 45 20 2a 65 67 6f 75 74 | 2c 20 2a 6d 63 69 6c 72 |E *egout|, *mcilr|
|00003b80| 6f 79 28 29 2c 20 2a 70 | 6f 70 65 6e 28 29 3b 0a |oy(), *p|open();.|
|00003b90| 63 68 61 72 20 2a 73 74 | 72 63 68 72 28 29 2c 20 |char *st|rchr(), |
|00003ba0| 2a 73 74 72 63 70 79 28 | 29 2c 20 2a 73 74 72 6e |*strcpy(|), *strn|
|00003bb0| 63 70 79 28 29 2c 20 2a | 73 74 72 70 62 72 6b 28 |cpy(), *|strpbrk(|
|00003bc0| 29 2c 20 2a 6d 61 6c 6c | 6f 63 28 29 3b 0a 63 68 |), *mall|oc();.ch|
|00003bd0| 61 72 20 2a 66 6f 6c 64 | 28 29 2c 20 2a 73 79 73 |ar *fold|(), *sys|
|00003be0| 35 66 6f 6c 64 28 29 3b | 0a 0a 6d 61 69 6e 20 28 |5fold();|..main (|
|00003bf0| 20 61 72 67 63 2c 20 61 | 72 67 76 20 29 0a 09 69 | argc, a|rgv )..i|
|00003c00| 6e 74 20 61 72 67 63 3b | 20 63 68 61 72 20 2a 61 |nt argc;| char *a|
|00003c10| 72 67 76 5b 5d 3b 0a 7b | 0a 20 20 20 20 20 20 20 |rgv[];.{|. |
|00003c20| 20 69 6e 74 20 63 3b 0a | 20 20 20 20 20 20 20 20 | int c;.| |
|00003c30| 69 6e 74 20 65 72 72 66 | 6c 61 67 20 3d 20 30 3b |int errf|lag = 0;|
|00003c40| 0a 20 20 20 20 20 20 20 | 20 69 6e 74 20 6f 6c 64 |. | int old|
|00003c50| 65 67 72 65 70 20 3d 20 | 30 3b 0a 0a 20 20 20 20 |egrep = |0;.. |
|00003c60| 20 20 20 20 77 68 69 6c | 65 20 28 20 28 63 20 3d | whil|e ( (c =|
|00003c70| 20 67 65 74 6f 70 74 20 | 28 20 61 72 67 63 2c 20 | getopt |( argc, |
|00003c80| 61 72 67 76 2c 20 22 62 | 63 68 69 65 3a 66 3a 6c |argv, "b|chie:f:l|
|00003c90| 6e 76 22 20 29 20 29 20 | 21 3d 20 45 4f 46 20 29 |nv" ) ) |!= EOF )|
|00003ca0| 0a 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.. | |
|00003cb0| 20 20 73 77 69 74 63 68 | 28 63 29 20 7b 0a 0a 09 | switch|(c) {...|
|00003cc0| 09 63 61 73 65 20 27 66 | 27 3a 0a 09 09 09 66 66 |.case 'f|':....ff|
|00003cd0| 6c 61 67 2b 2b 3b 0a 20 | 20 20 20 20 20 20 20 20 |lag++;. | |
|00003ce0| 20 20 20 20 20 20 20 63 | 61 73 65 20 27 62 27 3a | c|ase 'b':|
|00003cf0| 0a 09 09 63 61 73 65 20 | 27 6e 27 3a 0a 09 09 63 |...case |'n':...c|
|00003d00| 61 73 65 20 27 76 27 3a | 0a 09 09 09 6f 6c 64 65 |ase 'v':|....olde|
|00003d10| 67 72 65 70 2b 2b 3b 09 | 2f 2a 20 62 6f 79 65 72 |grep++;.|/* boyer|
|00003d20| 2d 6d 6f 6f 72 65 20 6f | 66 20 6c 69 74 74 6c 65 |-moore o|f little|
|00003d30| 20 68 65 6c 70 20 68 65 | 72 65 20 2a 2f 0a 20 20 | help he|re */. |
|00003d40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003d50| 20 20 20 20 20 20 63 6f | 6e 74 69 6e 75 65 3b 0a | co|ntinue;.|
|00003d60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003d70| 63 61 73 65 20 27 63 27 | 3a 0a 20 20 20 20 20 20 |case 'c'|:. |
|00003d80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003d90| 20 20 63 66 6c 61 67 2b | 2b 3b 0a 20 20 20 20 20 | cflag+|+;. |
|00003da0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003db0| 20 20 20 63 6f 6e 74 69 | 6e 75 65 3b 0a 20 20 20 | conti|nue;. |
|00003dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 63 61 73 | | cas|
|00003dd0| 65 20 27 65 27 3a 0a 20 | 20 20 20 20 20 20 20 20 |e 'e':. | |
|00003de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 65 | | e|
|00003df0| 66 6c 61 67 2b 2b 3b 0a | 20 20 20 20 20 20 20 20 |flag++;.| |
|00003e00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003e10| 70 61 74 74 65 72 6e 20 | 3d 20 6f 70 74 61 72 67 |pattern |= optarg|
|00003e20| 3b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;. | |
|00003e30| 20 20 20 20 20 20 20 20 | 20 20 63 6f 6e 74 69 6e | | contin|
|00003e40| 75 65 3b 0a 09 09 63 61 | 73 65 20 27 68 27 3a 0a |ue;...ca|se 'h':.|
|00003e50| 09 09 09 68 66 6c 61 67 | 2b 2b 3b 09 2f 2a 20 73 |...hflag|++;./* s|
|00003e60| 68 68 20 2e 2e 2e 20 66 | 6f 72 20 6e 65 77 73 68 |hh ... f|or newsh|
|00003e70| 6f 75 6e 64 73 20 2a 2f | 0a 09 09 09 63 6f 6e 74 |ounds */|....cont|
|00003e80| 69 6e 75 65 3b 0a 20 20 | 20 20 20 20 20 20 20 20 |inue;. | |
|00003e90| 20 20 20 20 20 20 63 61 | 73 65 20 27 69 27 3a 0a | ca|se 'i':.|
|00003ea0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003eb0| 20 20 20 20 20 20 20 20 | 69 66 6c 61 67 2b 2b 3b | |iflag++;|
|00003ec0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00003ed0| 20 20 20 20 20 20 20 20 | 20 63 6f 6e 74 69 6e 75 | | continu|
|00003ee0| 65 3b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e;. | |
|00003ef0| 20 20 20 63 61 73 65 20 | 27 6c 27 3a 0a 20 20 20 | case |'l':. |
|00003f00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f10| 20 20 20 20 20 6c 66 6c | 61 67 2b 2b 3b 0a 20 20 | lfl|ag++;. |
|00003f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f30| 20 20 20 20 20 20 63 6f | 6e 74 69 6e 75 65 3b 0a | co|ntinue;.|
|00003f40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f50| 63 61 73 65 20 27 3f 27 | 3a 0a 20 20 20 20 20 20 |case '?'|:. |
|00003f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f70| 20 20 65 72 72 66 6c 61 | 67 2b 2b 3b 0a 20 20 20 | errfla|g++;. |
|00003f80| 20 20 20 20 20 09 7d 0a | 20 20 20 20 20 20 20 20 | .}.| |
|00003f90| 61 72 67 63 20 2d 3d 20 | 6f 70 74 69 6e 64 3b 0a |argc -= |optind;.|
|00003fa0| 20 20 20 20 20 20 20 20 | 69 66 20 28 20 65 72 72 | |if ( err|
|00003fb0| 66 6c 61 67 20 7c 7c 20 | 28 28 61 72 67 63 20 3c |flag || |((argc <|
|00003fc0| 3d 20 30 29 20 26 26 20 | 21 66 66 6c 61 67 29 20 |= 0) && |!fflag) |
|00003fd0| 29 0a 09 09 6f 6f 70 73 | 20 28 20 22 75 73 61 67 |)...oops| ( "usag|
|00003fe0| 65 3a 20 65 67 72 65 70 | 20 5b 2d 62 63 69 6c 6e |e: egrep| [-bciln|
|00003ff0| 76 5d 20 5b 2d 65 20 65 | 78 70 5d 20 5b 2d 66 20 |v] [-e e|xp] [-f |
|00004000| 66 69 6c 65 5d 20 5b 73 | 74 72 69 6e 67 73 5d 20 |file] [s|trings] |
|00004010| 5b 66 69 6c 65 5d 22 20 | 29 3b 0a 20 20 20 20 20 |[file]" |);. |
|00004020| 20 20 20 69 66 20 28 20 | 21 65 66 6c 61 67 20 29 | if ( |!eflag )|
|00004030| 20 7b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | {. | |
|00004040| 20 20 20 70 61 74 74 65 | 72 6e 20 3d 20 61 72 67 | patte|rn = arg|
|00004050| 76 5b 6f 70 74 69 6e 64 | 2b 2b 5d 3b 0a 20 20 20 |v[optind|++];. |
|00004060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 61 72 67 | | arg|
|00004070| 63 2d 2d 3b 0a 20 20 20 | 20 20 20 20 20 7d 0a 09 |c--;. | }..|
|00004080| 69 66 20 28 20 6f 6c 64 | 65 67 72 65 70 20 7c 7c |if ( old|egrep |||
|00004090| 20 28 73 74 72 63 68 72 | 20 28 20 70 61 74 74 65 | (strchr| ( patte|
|000040a0| 72 6e 2c 20 27 5c 6e 27 | 20 29 20 21 3d 20 4e 55 |rn, '\n'| ) != NU|
|000040b0| 4c 4c 29 20 29 20 7b 0a | 09 09 65 78 65 63 76 70 |LL) ) {.|..execvp|
|000040c0| 20 28 20 45 47 52 45 50 | 2c 20 61 72 67 76 20 29 | ( EGREP|, argv )|
|000040d0| 3b 0a 09 09 6f 6f 70 73 | 20 28 20 22 63 61 6e 27 |;...oops| ( "can'|
|000040e0| 74 20 65 78 65 63 20 6f | 6c 64 20 27 65 67 72 65 |t exec o|ld 'egre|
|000040f0| 70 27 22 20 29 3b 0a 09 | 7d 0a 20 20 20 20 20 20 |p'" );..|}. |
|00004100| 20 20 69 66 20 28 20 69 | 66 6c 61 67 20 29 20 7b | if ( i|flag ) {|
|00004110| 0a 09 09 73 74 72 63 70 | 79 20 28 20 70 61 74 74 |...strcp|y ( patt|
|00004120| 65 72 6e 2c 20 66 6f 6c | 64 20 28 20 70 61 74 74 |ern, fol|d ( patt|
|00004130| 65 72 6e 20 29 20 29 3b | 0a 09 7d 0a 09 69 66 20 |ern ) );|..}..if |
|00004140| 28 20 73 74 72 70 62 72 | 6b 20 28 20 70 61 74 74 |( strpbr|k ( patt|
|00004150| 65 72 6e 2c 20 22 5e 24 | 2e 5b 5d 28 29 3f 2b 2a |ern, "^$|.[]()?+*|
|00004160| 7c 5c 5c 22 20 29 20 3d | 3d 20 4e 55 4c 4c 20 29 ||\\" ) =|= NULL )|
|00004170| 20 7b 09 2f 2a 20 64 6f | 20 62 6f 79 65 72 2d 6d | {./* do| boyer-m|
|00004180| 6f 6f 72 65 20 6f 6e 6c | 79 20 2a 2f 0a 09 09 62 |oore onl|y */...b|
|00004190| 6f 79 66 6c 61 67 2b 2b | 3b 0a 09 09 72 78 66 6c |oyflag++|;...rxfl|
|000041a0| 61 67 20 3d 20 30 3b 0a | 09 09 70 61 74 62 6f 79 |ag = 0;.|..patboy|
|000041b0| 20 3d 20 70 61 74 74 65 | 72 6e 3b 0a 09 7d 0a 09 | = patte|rn;..}..|
|000041c0| 65 6c 73 65 20 7b 20 09 | 0a 09 09 2f 2a 0a 09 09 |else { .|.../*...|
|000041d0| 20 20 20 20 66 69 72 73 | 74 20 63 6f 6d 70 69 6c | firs|t compil|
|000041e0| 65 20 61 20 66 61 6b 65 | 20 72 65 67 65 78 70 20 |e a fake| regexp |
|000041f0| 74 6f 20 69 73 6f 6c 61 | 74 65 20 6c 6f 6e 67 65 |to isola|te longe|
|00004200| 73 74 0a 09 09 20 20 20 | 20 6d 65 74 61 63 68 61 |st... | metacha|
|00004210| 72 61 63 74 65 72 2d 66 | 72 65 65 20 73 74 72 69 |racter-f|ree stri|
|00004220| 6e 67 0a 09 09 2a 2f 0a | 09 09 7b 0a 09 09 09 63 |ng...*/.|..{....c|
|00004230| 68 61 72 20 2a 64 75 6d | 6d 79 70 3b 0a 09 09 09 |har *dum|myp;....|
|00004240| 64 75 6d 6d 79 70 20 3d | 20 6d 61 6c 6c 6f 63 20 |dummyp =| malloc |
|00004250| 28 20 28 75 6e 73 69 67 | 6e 65 64 29 20 73 74 72 |( (unsig|ned) str|
|00004260| 6c 65 6e 20 28 20 70 61 | 74 74 65 72 6e 20 29 20 |len ( pa|ttern ) |
|00004270| 2b 20 35 20 29 3b 0a 09 | 09 09 73 70 72 69 6e 74 |+ 5 );..|..sprint|
|00004280| 66 20 28 20 64 75 6d 6d | 79 70 2c 20 22 28 2e 29 |f ( dumm|yp, "(.)|
|00004290| 2a 25 73 22 2c 20 70 61 | 74 74 65 72 6e 20 29 3b |*%s", pa|ttern );|
|000042a0| 0a 09 09 09 72 73 70 65 | 6e 63 65 72 20 3d 20 72 |....rspe|ncer = r|
|000042b0| 65 67 63 6f 6d 70 20 28 | 20 64 75 6d 6d 79 70 20 |egcomp (| dummyp |
|000042c0| 29 3b 0a 09 09 7d 0a 09 | 09 69 66 20 28 20 72 73 |);...}..|.if ( rs|
|000042d0| 70 65 6e 63 65 72 20 2d | 3e 20 72 65 67 6d 75 73 |pencer -|> regmus|
|000042e0| 74 20 3d 3d 20 4e 55 4c | 4c 20 29 20 7b 09 09 2f |t == NUL|L ) {../|
|000042f0| 2a 20 70 61 74 74 65 72 | 6e 20 74 6f 6f 20 63 6f |* patter|n too co|
|00004300| 6d 70 6c 69 63 61 74 65 | 64 20 2a 2f 0a 09 09 09 |mplicate|d */....|
|00004310| 65 78 65 63 76 70 20 28 | 20 45 47 52 45 50 2c 20 |execvp (| EGREP, |
|00004320| 61 72 67 76 20 29 3b 0a | 09 09 09 6f 6f 70 73 20 |argv );.|...oops |
|00004330| 28 20 22 63 61 6e 27 74 | 20 65 78 65 63 20 6f 6c |( "can't| exec ol|
|00004340| 64 20 27 65 67 72 65 70 | 27 22 20 29 3b 0a 09 09 |d 'egrep|'" );...|
|00004350| 7d 0a 09 09 70 61 74 62 | 6f 79 20 3d 20 72 73 70 |}...patb|oy = rsp|
|00004360| 65 6e 63 65 72 20 2d 3e | 20 72 65 67 6d 75 73 74 |encer ->| regmust|
|00004370| 3b 0a 09 09 69 66 20 28 | 20 28 72 73 70 65 6e 63 |;...if (| (rspenc|
|00004380| 65 72 20 3d 20 72 65 67 | 63 6f 6d 70 20 28 20 70 |er = reg|comp ( p|
|00004390| 61 74 74 65 72 6e 20 29 | 29 20 3d 3d 20 4e 55 4c |attern )|) == NUL|
|000043a0| 4c 20 29 0a 09 09 09 6f | 6f 70 73 20 28 20 22 65 |L )....o|ops ( "e|
|000043b0| 67 72 65 70 3a 20 72 65 | 67 63 6f 6d 70 20 66 61 |grep: re|gcomp fa|
|000043c0| 69 6c 75 72 65 22 20 29 | 3b 0a 09 7d 0a 09 67 6f |ilure" )|;..}..go|
|000043d0| 73 70 65 72 20 28 20 70 | 61 74 62 6f 79 20 29 3b |sper ( p|atboy );|
|000043e0| 0a 20 20 20 20 20 20 20 | 20 61 72 67 76 20 3d 20 |. | argv = |
|000043f0| 26 61 72 67 76 5b 6f 70 | 74 69 6e 64 5d 3b 0a 20 |&argv[op|tind];. |
|00004400| 20 20 20 20 20 20 20 6e | 66 69 6c 65 20 3d 20 61 | n|file = a|
|00004410| 72 67 63 3b 0a 20 20 20 | 20 20 20 20 20 69 66 20 |rgc;. | if |
|00004420| 28 20 61 72 67 63 20 3c | 3d 20 30 20 29 20 7b 09 |( argc <|= 0 ) {.|
|00004430| 09 2f 2a 20 70 72 6f 63 | 65 73 73 20 73 74 64 69 |./* proc|ess stdi|
|00004440| 6e 20 2a 2f 0a 20 20 20 | 20 20 20 20 20 20 20 20 |n */. | |
|00004450| 20 20 20 20 20 69 66 20 | 28 20 6c 66 6c 61 67 20 | if |( lflag |
|00004460| 29 0a 09 09 09 65 78 69 | 74 20 28 20 31 20 29 3b |)....exi|t ( 1 );|
|00004470| 0a 09 09 66 64 20 3d 20 | 30 3b 0a 09 09 69 66 20 |...fd = |0;...if |
|00004480| 28 20 21 62 6f 79 66 6c | 61 67 20 29 0a 09 09 09 |( !boyfl|ag )....|
|00004490| 69 66 20 28 20 28 65 67 | 6f 75 74 20 3d 20 6d 63 |if ( (eg|out = mc|
|000044a0| 69 6c 72 6f 79 20 28 20 | 28 63 68 61 72 20 2a 29 |ilroy ( |(char *)|
|000044b0| 20 4e 55 4c 4c 20 29 29 | 20 3d 3d 20 4e 55 4c 4c | NULL ))| == NULL|
|000044c0| 20 29 0a 09 09 09 09 6f | 6f 70 73 20 28 20 22 65 | ).....o|ops ( "e|
|000044d0| 67 72 65 70 3a 20 6e 6f | 20 70 72 6f 63 65 73 73 |grep: no| process|
|000044e0| 65 73 22 20 29 3b 0a 20 | 20 20 20 20 20 20 20 20 |es" );. | |
|000044f0| 20 20 20 20 20 20 20 62 | 6f 79 65 72 6d 6f 6f 72 | b|oyermoor|
|00004500| 65 20 28 20 28 63 68 61 | 72 20 2a 29 20 4e 55 4c |e ( (cha|r *) NUL|
|00004510| 4c 2c 20 70 61 74 62 6f | 79 20 29 3b 0a 09 09 69 |L, patbo|y );...i|
|00004520| 66 20 28 20 21 62 6f 79 | 66 6c 61 67 20 29 0a 09 |f ( !boy|flag )..|
|00004530| 09 09 70 63 6c 6f 73 65 | 20 28 20 65 67 6f 75 74 |..pclose| ( egout|
|00004540| 20 29 3b 0a 20 20 20 20 | 20 20 20 20 7d 0a 20 20 | );. | }. |
|00004550| 20 20 20 20 20 20 65 6c | 73 65 20 7b 0a 20 20 20 | el|se {. |
|00004560| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 77 68 69 | | whi|
|00004570| 6c 65 20 28 20 2d 2d 61 | 72 67 63 20 3e 3d 20 30 |le ( --a|rgc >= 0|
|00004580| 20 29 20 7b 0a 20 20 20 | 20 20 20 20 20 20 20 20 | ) {. | |
|00004590| 20 20 20 20 20 09 69 66 | 20 28 20 28 66 64 20 3d | .if| ( (fd =|
|000045a0| 20 6f 70 65 6e 20 28 20 | 2a 61 72 67 76 2c 20 30 | open ( |*argv, 0|
|000045b0| 20 29 29 20 3c 3d 20 30 | 20 29 20 7b 0a 20 20 20 | )) <= 0| ) {. |
|000045c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000045d0| 20 20 20 20 20 09 66 70 | 72 69 6e 74 66 20 28 20 | .fp|rintf ( |
|000045e0| 73 74 64 65 72 72 2c 20 | 22 65 67 72 65 70 3a 20 |stderr, |"egrep: |
|000045f0| 63 61 6e 27 74 20 6f 70 | 65 6e 20 25 73 5c 6e 22 |can't op|en %s\n"|
|00004600| 2c 20 2a 61 72 67 76 20 | 29 3b 0a 20 20 20 20 20 |, *argv |);. |
|00004610| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004620| 20 20 20 09 6e 73 75 63 | 63 65 73 73 20 3d 20 32 | .nsuc|cess = 2|
|00004630| 3b 0a 09 09 09 09 61 72 | 67 76 2b 2b 3b 0a 09 09 |;.....ar|gv++;...|
|00004640| 09 09 63 6f 6e 74 69 6e | 75 65 3b 0a 09 09 09 7d |..contin|ue;....}|
|00004650| 0a 09 09 09 69 66 20 28 | 20 21 62 6f 79 66 6c 61 |....if (| !boyfla|
|00004660| 67 20 29 20 7b 0a 09 09 | 09 09 66 73 74 61 74 20 |g ) {...|..fstat |
|00004670| 28 20 66 64 2c 20 26 73 | 74 62 75 66 20 29 3b 0a |( fd, &s|tbuf );.|
|00004680| 09 09 09 09 69 66 20 28 | 20 73 74 62 75 66 2e 73 |....if (| stbuf.s|
|00004690| 74 5f 73 69 7a 65 20 3c | 20 46 53 49 5a 45 20 29 |t_size <| FSIZE )|
|000046a0| 0a 09 09 09 09 09 72 78 | 66 6c 61 67 20 3d 20 31 |......rx|flag = 1|
|000046b0| 3b 0a 09 09 09 09 65 6c | 73 65 20 7b 0a 09 09 09 |;.....el|se {....|
|000046c0| 09 09 72 78 66 6c 61 67 | 20 3d 20 30 3b 0a 09 09 |..rxflag| = 0;...|
|000046d0| 09 09 09 69 66 20 28 20 | 28 65 67 6f 75 74 20 3d |...if ( |(egout =|
|000046e0| 20 6d 63 69 6c 72 6f 79 | 20 28 20 2a 61 72 67 76 | mcilroy| ( *argv|
|000046f0| 20 29 29 20 3d 3d 20 4e | 55 4c 4c 20 29 0a 09 09 | )) == N|ULL )...|
|00004700| 09 09 09 09 6f 6f 70 73 | 20 28 20 22 65 67 72 65 |....oops| ( "egre|
|00004710| 70 3a 20 6e 6f 20 70 72 | 6f 63 65 73 73 65 73 22 |p: no pr|ocesses"|
|00004720| 20 29 3b 0a 09 09 09 09 | 7d 0a 09 09 09 7d 0a 20 | );.....|}....}. |
|00004730| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004740| 20 20 20 20 20 20 20 62 | 6f 79 65 72 6d 6f 6f 72 | b|oyermoor|
|00004750| 65 20 28 20 2a 61 72 67 | 76 2c 20 70 61 74 62 6f |e ( *arg|v, patbo|
|00004760| 79 20 29 3b 0a 09 09 09 | 69 66 20 28 20 21 62 6f |y );....|if ( !bo|
|00004770| 79 66 6c 61 67 20 26 26 | 20 21 72 78 66 6c 61 67 |yflag &&| !rxflag|
|00004780| 20 29 20 7b 0a 09 09 09 | 09 66 66 6c 75 73 68 20 | ) {....|.fflush |
|00004790| 28 20 65 67 6f 75 74 20 | 29 3b 0a 09 09 09 09 70 |( egout |);.....p|
|000047a0| 63 6c 6f 73 65 20 28 20 | 65 67 6f 75 74 20 29 3b |close ( |egout );|
|000047b0| 0a 09 09 09 7d 0a 09 09 | 09 63 6c 6f 73 65 20 28 |....}...|.close (|
|000047c0| 20 66 64 20 29 3b 0a 09 | 09 09 61 72 67 76 2b 2b | fd );..|..argv++|
|000047d0| 3b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;. | |
|000047e0| 20 20 7d 0a 09 7d 0a 20 | 20 20 20 20 20 20 20 65 | }..}. | e|
|000047f0| 78 69 74 20 28 20 28 6e | 73 75 63 63 65 73 73 20 |xit ( (n|success |
|00004800| 3d 3d 20 32 29 20 3f 20 | 32 20 3a 20 28 6e 73 75 |== 2) ? |2 : (nsu|
|00004810| 63 63 65 73 73 20 3d 3d | 20 30 29 20 29 3b 0a 7d |ccess ==| 0) );.}|
|00004820| 0a 0a 62 6f 79 65 72 6d | 6f 6f 72 65 20 28 20 66 |..boyerm|oore ( f|
|00004830| 69 6c 65 2c 20 70 61 74 | 74 65 72 6e 20 29 09 2f |ile, pat|tern )./|
|00004840| 2a 20 22 72 65 61 63 68 | 20 6f 75 74 20 61 6e 64 |* "reach| out and|
|00004850| 20 62 6f 79 65 72 2d 6d | 6f 6f 72 65 20 73 65 61 | boyer-m|oore sea|
|00004860| 72 63 68 20 73 6f 6d 65 | 6f 6e 65 22 20 2a 2f 0a |rch some|one" */.|
|00004870| 09 63 68 61 72 20 2a 66 | 69 6c 65 2c 20 2a 70 61 |.char *f|ile, *pa|
|00004880| 74 74 65 72 6e 3b 09 2f | 2a 20 2d 2d 20 73 6f 6f |ttern;./|* -- soo|
|00004890| 6e 2d 74 6f 2d 62 65 2d | 70 6f 70 75 6c 61 72 20 |n-to-be-|popular |
|000048a0| 62 75 6d 70 65 72 20 73 | 74 69 63 6b 65 72 20 2a |bumper s|ticker *|
|000048b0| 2f 0a 7b 0a 09 72 65 67 | 69 73 74 65 72 20 63 68 |/.{..reg|ister ch|
|000048c0| 61 72 20 2a 6b 2c 20 2a | 73 74 72 65 6e 64 2c 20 |ar *k, *|strend, |
|000048d0| 2a 73 3b 0a 09 72 65 67 | 69 73 74 65 72 20 69 6e |*s;..reg|ister in|
|000048e0| 74 20 6a 3b 0a 09 69 6e | 74 20 70 61 74 6c 65 6e |t j;..in|t patlen|
|000048f0| 3b 0a 09 63 68 61 72 20 | 2a 74 3b 0a 09 63 68 61 |;..char |*t;..cha|
|00004900| 72 20 2a 67 6f 74 61 6d | 61 74 63 68 28 29 3b 0a |r *gotam|atch();.|
|00004910| 09 69 6e 74 20 6e 6c 65 | 66 74 6f 76 65 72 2c 20 |.int nle|ftover, |
|00004920| 63 6f 75 6e 74 3b 0a 0a | 09 70 61 74 6c 65 6e 20 |count;..|.patlen |
|00004930| 3d 20 73 74 72 6c 65 6e | 20 28 20 70 61 74 74 65 |= strlen| ( patte|
|00004940| 72 6e 20 29 3b 0a 09 6e | 6c 65 66 74 6f 76 65 72 |rn );..n|leftover|
|00004950| 20 3d 20 6e 6d 61 74 63 | 68 20 3d 20 30 3b 0a 0a | = nmatc|h = 0;..|
|00004960| 23 69 66 64 65 66 20 56 | 37 0a 23 64 65 66 69 6e |#ifdef V|7.#defin|
|00004970| 65 20 72 65 61 64 20 78 | 72 65 61 64 0a 23 65 6e |e read x|read.#en|
|00004980| 64 69 66 0a 09 77 68 69 | 6c 65 20 28 20 28 63 6f |dif..whi|le ( (co|
|00004990| 75 6e 74 20 3d 20 72 65 | 61 64 20 28 20 66 64 2c |unt = re|ad ( fd,|
|000049a0| 20 73 74 72 20 2b 20 6e | 6c 65 66 74 6f 76 65 72 | str + n|leftover|
|000049b0| 2c 20 42 55 46 53 49 5a | 45 20 2d 20 6e 6c 65 66 |, BUFSIZ|E - nlef|
|000049c0| 74 6f 76 65 72 20 29 29 | 20 3e 20 30 20 29 20 7b |tover ))| > 0 ) {|
|000049d0| 0a 0a 23 75 6e 64 65 66 | 20 72 65 61 64 0a 09 09 |..#undef| read...|
|000049e0| 63 6f 75 6e 74 20 2b 3d | 20 6e 6c 65 66 74 6f 76 |count +=| nleftov|
|000049f0| 65 72 3b 0a 09 09 69 66 | 20 28 20 63 6f 75 6e 74 |er;...if| ( count|
|00004a00| 20 21 3d 20 42 55 46 53 | 49 5a 45 20 26 26 20 66 | != BUFS|IZE && f|
|00004a10| 64 20 21 3d 20 30 29 0a | 09 09 09 73 74 72 5b 63 |d != 0).|...str[c|
|00004a20| 6f 75 6e 74 2b 2b 5d 20 | 3d 20 4e 4c 3b 09 2f 2a |ount++] |= NL;./*|
|00004a30| 20 69 6e 73 75 72 61 6e | 63 65 20 66 6f 72 20 62 | insuran|ce for b|
|00004a40| 72 6f 6b 65 6e 20 6c 61 | 73 74 20 6c 69 6e 65 20 |roken la|st line |
|00004a50| 2a 2f 0a 09 09 73 74 72 | 5b 63 6f 75 6e 74 5d 20 |*/...str|[count] |
|00004a60| 3d 20 30 3b 0a 09 09 66 | 6f 72 20 28 20 6a 20 3d |= 0;...f|or ( j =|
|00004a70| 20 63 6f 75 6e 74 20 2d | 20 31 3b 20 73 74 72 5b | count -| 1; str[|
|00004a80| 6a 5d 20 21 3d 20 4e 4c | 20 26 26 20 6a 20 3e 3d |j] != NL| && j >=|
|00004a90| 20 30 3b 20 29 0a 09 09 | 09 6a 2d 2d 3b 0a 09 09 | 0; )...|.j--;...|
|00004aa0| 69 66 20 28 20 6a 20 3c | 20 30 20 29 20 7b 09 09 |if ( j <| 0 ) {..|
|00004ab0| 09 2f 2a 20 62 72 65 61 | 6b 20 75 70 20 6c 6f 6e |./* brea|k up lon|
|00004ac0| 67 20 6c 69 6e 65 20 2a | 2f 0a 09 09 09 73 74 72 |g line *|/....str|
|00004ad0| 5b 63 6f 75 6e 74 5d 20 | 3d 20 4e 4c 3b 0a 09 09 |[count] |= NL;...|
|00004ae0| 09 73 74 72 5b 2b 2b 63 | 6f 75 6e 74 5d 20 3d 20 |.str[++c|ount] = |
|00004af0| 45 4f 53 3b 0a 09 09 09 | 73 74 72 65 6e 64 20 3d |EOS;....|strend =|
|00004b00| 20 73 74 72 20 2b 20 63 | 6f 75 6e 74 3b 0a 09 09 | str + c|ount;...|
|00004b10| 09 6c 69 6e 65 74 65 6d | 70 5b 30 5d 20 3d 20 45 |.linetem|p[0] = E|
|00004b20| 4f 53 3b 0a 09 09 09 6e | 6c 65 66 74 6f 76 65 72 |OS;....n|leftover|
|00004b30| 20 3d 20 30 3b 0a 09 09 | 7d 0a 09 09 65 6c 73 65 | = 0;...|}...else|
|00004b40| 20 7b 09 09 09 09 2f 2a | 20 73 61 76 65 20 70 61 | {..../*| save pa|
|00004b50| 72 74 69 61 6c 20 6c 69 | 6e 65 20 2a 2f 0a 09 09 |rtial li|ne */...|
|00004b60| 09 73 74 72 65 6e 64 20 | 3d 20 73 74 72 20 2b 20 |.strend |= str + |
|00004b70| 6a 3b 0a 09 09 09 6e 6c | 65 66 74 6f 76 65 72 20 |j;....nl|eftover |
|00004b80| 3d 20 63 6f 75 6e 74 20 | 2d 20 6a 20 2d 20 31 3b |= count |- j - 1;|
|00004b90| 0a 09 09 09 73 74 72 6e | 63 70 79 20 28 20 6c 69 |....strn|cpy ( li|
|00004ba0| 6e 65 74 65 6d 70 2c 20 | 73 74 72 20 2b 20 6a 20 |netemp, |str + j |
|00004bb0| 2b 20 31 2c 20 6e 6c 65 | 66 74 6f 76 65 72 20 29 |+ 1, nle|ftover )|
|00004bc0| 3b 0a 09 09 7d 0a 09 09 | 6b 20 3d 20 73 74 72 20 |;...}...|k = str |
|00004bd0| 2b 20 70 61 74 6c 65 6e | 20 2d 20 31 3b 0a 0a 09 |+ patlen| - 1;...|
|00004be0| 09 66 6f 72 20 28 20 3b | 20 3b 20 29 20 7b 0a 09 |.for ( ;| ; ) {..|
|00004bf0| 09 09 2f 2a 0a 09 09 09 | 20 20 20 20 66 6f 72 20 |../*....| for |
|00004c00| 61 20 6c 61 72 67 65 20 | 63 6c 61 73 73 20 6f 66 |a large |class of|
|00004c10| 20 70 61 74 74 65 72 6e | 73 2c 20 75 70 77 61 72 | pattern|s, upwar|
|00004c20| 64 73 20 6f 66 20 38 30 | 25 20 6f 66 20 0a 09 09 |ds of 80|% of ...|
|00004c30| 09 20 20 20 20 6d 61 74 | 63 68 20 74 69 6d 65 20 |. mat|ch time |
|00004c40| 69 73 20 73 70 65 6e 74 | 20 6f 6e 20 74 68 65 20 |is spent| on the |
|00004c50| 6e 65 78 74 20 6c 69 6e | 65 2e 20 20 0a 09 09 09 |next lin|e. ....|
|00004c60| 20 20 20 20 77 65 20 62 | 65 61 74 20 65 78 69 73 | we b|eat exis|
|00004c70| 74 69 6e 67 20 6d 69 63 | 72 6f 63 6f 64 65 20 28 |ting mic|rocode (|
|00004c80| 76 61 78 20 27 6d 61 74 | 63 68 63 27 29 20 74 68 |vax 'mat|chc') th|
|00004c90| 69 73 20 77 61 79 2e 0a | 09 09 09 2a 2f 0a 23 69 |is way..|...*/.#i|
|00004ca0| 66 6e 64 65 66 20 56 37 | 0a 09 09 09 77 68 69 6c |fndef V7|....whil|
|00004cb0| 65 20 28 20 28 6b 20 2b | 3d 20 64 65 6c 74 61 30 |e ( (k +|= delta0|
|00004cc0| 5b 2a 28 75 6e 73 69 67 | 6e 65 64 20 63 68 61 72 |[*(unsig|ned char|
|00004cd0| 20 2a 29 6b 5d 29 20 3c | 20 73 74 72 65 6e 64 20 | *)k]) <| strend |
|00004ce0| 29 0a 09 09 09 09 3b 09 | 0a 23 65 6c 73 65 0a 09 |).....;.|.#else..|
|00004cf0| 09 09 77 68 69 6c 65 20 | 28 20 28 6b 20 2b 3d 20 |..while |( (k += |
|00004d00| 64 65 6c 74 61 30 5b 2a | 28 63 68 61 72 20 2a 29 |delta0[*|(char *)|
|00004d10| 6b 20 26 20 30 33 37 37 | 5d 29 20 3c 20 73 74 72 |k & 0377|]) < str|
|00004d20| 65 6e 64 20 29 0a 09 09 | 09 09 3b 0a 23 65 6e 64 |end )...|..;.#end|
|00004d30| 69 66 0a 09 09 09 69 66 | 20 28 20 6b 20 3c 20 28 |if....if| ( k < (|
|00004d40| 73 74 72 20 2b 20 4c 41 | 52 47 45 29 20 29 0a 09 |str + LA|RGE) )..|
|00004d50| 09 09 09 62 72 65 61 6b | 3b 0a 09 09 09 6b 20 2d |...break|;....k -|
|00004d60| 3d 20 4c 41 52 47 45 3b | 0a 0a 09 09 09 6a 20 3d |= LARGE;|.....j =|
|00004d70| 20 70 61 74 6c 65 6e 20 | 2d 20 31 3b 0a 09 09 09 | patlen |- 1;....|
|00004d80| 73 20 3d 20 6b 20 2d 20 | 31 3b 0a 09 09 09 77 68 |s = k - |1;....wh|
|00004d90| 69 6c 65 20 28 20 63 6d | 61 70 5b 2a 73 2d 2d 5d |ile ( cm|ap[*s--]|
|00004da0| 20 3d 3d 20 70 61 74 74 | 65 72 6e 5b 2d 2d 6a 5d | == patt|ern[--j]|
|00004db0| 20 29 0a 09 09 09 09 3b | 0a 09 09 09 2f 2a 0a 09 | ).....;|..../*..|
|00004dc0| 09 09 20 20 20 20 64 65 | 6c 74 61 2d 6c 65 73 73 |.. de|lta-less|
|00004dd0| 20 73 68 6f 72 74 63 75 | 74 20 66 6f 72 20 6c 69 | shortcu|t for li|
|00004de0| 74 65 72 61 74 69 2c 20 | 62 75 74 20 0a 09 09 09 |terati, |but ....|
|00004df0| 20 20 20 20 73 68 6f 72 | 74 20 73 68 72 69 66 74 | shor|t shrift|
|00004e00| 20 66 6f 72 20 67 65 6e | 65 74 69 63 20 65 6e 67 | for gen|etic eng|
|00004e10| 69 6e 65 65 72 73 2e 0a | 09 09 09 2a 2f 0a 09 09 |ineers..|...*/...|
|00004e20| 09 69 66 20 28 20 6a 20 | 3e 3d 20 30 20 29 0a 09 |.if ( j |>= 0 )..|
|00004e30| 09 09 09 6b 2b 2b 3b 0a | 09 09 09 65 6c 73 65 20 |...k++;.|...else |
|00004e40| 7b 09 09 09 2f 2a 20 73 | 75 62 6d 61 74 63 68 20 |{.../* s|ubmatch |
|00004e50| 2a 2f 0a 09 09 09 09 74 | 20 3d 20 6b 3b 0a 09 09 |*/.....t| = k;...|
|00004e60| 09 09 73 20 3d 20 6b 20 | 2d 20 70 61 74 6c 65 6e |..s = k |- patlen|
|00004e70| 20 2b 20 31 3b 0a 09 09 | 09 09 64 6f 20 0a 09 09 | + 1;...|..do ...|
|00004e80| 09 09 09 3b 0a 09 09 09 | 09 77 68 69 6c 65 20 28 |...;....|.while (|
|00004e90| 20 2a 73 20 21 3d 20 4e | 4c 20 26 26 20 2d 2d 73 | *s != N|L && --s|
|00004ea0| 20 3e 3d 20 73 74 72 20 | 29 3b 20 0a 09 09 09 09 | >= str |); .....|
|00004eb0| 6b 20 3d 20 73 20 2b 20 | 31 3b 09 2f 2a 20 61 74 |k = s + |1;./* at|
|00004ec0| 20 6c 69 6e 65 20 73 74 | 61 72 74 20 2a 2f 0a 0a | line st|art */..|
|00004ed0| 09 09 09 09 69 66 20 28 | 20 62 6f 79 66 6c 61 67 |....if (| boyflag|
|00004ee0| 20 29 20 7b 0a 09 09 09 | 09 09 69 66 20 28 20 28 | ) {....|..if ( (|
|00004ef0| 6b 20 3d 20 67 6f 74 61 | 6d 61 74 63 68 20 28 20 |k = gota|match ( |
|00004f00| 66 69 6c 65 2c 20 6b 20 | 29 29 20 3d 3d 20 4e 55 |file, k |)) == NU|
|00004f10| 4c 4c 20 29 0a 09 09 09 | 09 09 09 72 65 74 75 72 |LL )....|...retur|
|00004f20| 6e 3b 0a 09 09 09 09 7d | 0a 09 09 09 09 65 6c 73 |n;.....}|.....els|
|00004f30| 65 20 69 66 20 28 20 21 | 72 78 66 6c 61 67 20 29 |e if ( !|rxflag )|
|00004f40| 20 7b 09 2f 2a 20 66 6f | 62 20 6f 66 66 20 74 6f | {./* fo|b off to|
|00004f50| 20 65 67 72 65 70 20 2a | 2f 0a 09 09 09 09 09 64 | egrep *|/......d|
|00004f60| 6f 0a 09 09 09 09 09 09 | 70 75 74 63 20 28 20 2a |o.......|putc ( *|
|00004f70| 6b 2c 20 65 67 6f 75 74 | 20 29 3b 0a 09 09 09 09 |k, egout| );.....|
|00004f80| 09 77 68 69 6c 65 20 28 | 20 2a 6b 2b 2b 20 21 3d |.while (| *k++ !=|
|00004f90| 20 4e 4c 20 29 3b 0a 09 | 09 09 09 7d 0a 09 09 09 | NL );..|...}....|
|00004fa0| 09 65 6c 73 65 20 7b 09 | 09 09 09 2f 2a 20 72 65 |.else {.|.../* re|
|00004fb0| 67 65 78 65 63 28 29 20 | 77 61 6e 74 73 20 45 4f |gexec() |wants EO|
|00004fc0| 53 20 2a 2f 0a 09 09 09 | 09 09 73 20 3d 20 74 3b |S */....|..s = t;|
|00004fd0| 0a 09 09 09 09 09 64 6f | 0a 09 09 09 09 09 09 3b |......do|.......;|
|00004fe0| 0a 09 09 09 09 09 77 68 | 69 6c 65 20 28 20 2a 73 |......wh|ile ( *s|
|00004ff0| 2b 2b 20 21 3d 20 4e 4c | 20 29 3b 0a 09 09 09 09 |++ != NL| );.....|
|00005000| 09 2a 2d 2d 73 20 3d 20 | 45 4f 53 3b 0a 0a 09 09 |.*--s = |EOS;....|
|00005010| 09 09 09 69 66 20 28 20 | 72 65 67 65 78 65 63 20 |...if ( |regexec |
|00005020| 28 20 72 73 70 65 6e 63 | 65 72 2c 20 28 28 69 66 |( rspenc|er, ((if|
|00005030| 6c 61 67 29 20 3f 20 66 | 6f 6c 64 20 28 20 6b 20 |lag) ? f|old ( k |
|00005040| 29 20 3a 20 6b 29 20 29 | 20 3d 3d 20 31 20 29 20 |) : k) )| == 1 ) |
|00005050| 7b 0a 09 09 09 09 09 09 | 2a 73 20 3d 20 4e 4c 3b |{.......|*s = NL;|
|00005060| 0a 09 09 09 09 09 09 69 | 66 20 28 20 67 6f 74 61 |.......i|f ( gota|
|00005070| 6d 61 74 63 68 20 28 20 | 66 69 6c 65 2c 20 6b 20 |match ( |file, k |
|00005080| 29 20 3d 3d 20 4e 55 4c | 4c 20 29 0a 09 09 09 09 |) == NUL|L ).....|
|00005090| 09 09 09 72 65 74 75 72 | 6e 3b 0a 09 09 09 09 09 |...retur|n;......|
|000050a0| 7d 0a 09 09 09 09 09 2a | 73 20 3d 20 4e 4c 3b 0a |}......*|s = NL;.|
|000050b0| 09 09 09 09 09 6b 20 3d | 20 73 20 2b 20 31 3b 0a |.....k =| s + 1;.|
|000050c0| 09 09 09 09 7d 0a 09 09 | 09 09 69 66 20 28 20 6b |....}...|..if ( k|
|000050d0| 20 3e 3d 20 73 74 72 65 | 6e 64 20 29 0a 09 09 09 | >= stre|nd )....|
|000050e0| 09 09 62 72 65 61 6b 3b | 0a 09 09 09 7d 0a 09 09 |..break;|....}...|
|000050f0| 7d 0a 09 09 73 74 72 6e | 63 70 79 20 28 20 73 74 |}...strn|cpy ( st|
|00005100| 72 2c 20 6c 69 6e 65 74 | 65 6d 70 2c 20 6e 6c 65 |r, linet|emp, nle|
|00005110| 66 74 6f 76 65 72 20 29 | 3b 0a 09 7d 0a 09 69 66 |ftover )|;..}..if|
|00005120| 20 28 20 63 66 6c 61 67 | 20 26 26 20 28 62 6f 79 | ( cflag| && (boy|
|00005130| 66 6c 61 67 20 7c 7c 20 | 72 78 66 6c 61 67 29 20 |flag || |rxflag) |
|00005140| 29 20 7b 0a 09 09 69 66 | 20 28 20 6e 66 69 6c 65 |) {...if| ( nfile|
|00005150| 20 3e 20 31 20 29 0a 09 | 09 09 70 72 69 6e 74 66 | > 1 )..|..printf|
|00005160| 20 28 20 22 25 73 3a 22 | 2c 20 66 69 6c 65 20 29 | ( "%s:"|, file )|
|00005170| 3b 0a 09 09 70 72 69 6e | 74 66 20 28 20 22 25 6c |;...prin|tf ( "%l|
|00005180| 64 5c 6e 22 2c 20 6e 6d | 61 74 63 68 20 29 3b 0a |d\n", nm|atch );.|
|00005190| 09 7d 0a 7d 0a 0a 46 49 | 4c 45 20 2a 0a 6d 63 69 |.}.}..FI|LE *.mci|
|000051a0| 6c 72 6f 79 20 28 20 66 | 69 6c 65 20 29 09 2f 2a |lroy ( f|ile )./*|
|000051b0| 20 6f 70 65 6e 20 61 20 | 70 69 70 65 20 74 6f 20 | open a |pipe to |
|000051c0| 6f 6c 64 20 27 65 67 72 | 65 70 27 20 66 6f 72 20 |old 'egr|ep' for |
|000051d0| 6c 6f 6e 67 20 66 69 6c | 65 73 2c 20 2a 2f 0a 09 |long fil|es, */..|
|000051e0| 63 68 61 72 20 2a 66 69 | 6c 65 3b 09 2f 2a 20 2e |char *fi|le;./* .|
|000051f0| 2e 2e 20 77 68 65 72 65 | 20 72 65 67 65 78 70 28 |.. where| regexp(|
|00005200| 29 20 6d 69 67 68 74 20 | 62 65 20 69 6e 65 66 66 |) might |be ineff|
|00005210| 69 63 69 65 6e 74 20 2a | 2f 0a 7b 0a 23 69 66 64 |icient *|/.{.#ifd|
|00005220| 65 66 20 42 53 44 0a 09 | 69 6e 74 20 69 66 6c 61 |ef BSD..|int ifla|
|00005230| 67 73 61 76 65 20 3d 20 | 30 3b 0a 09 63 68 61 72 |gsave = |0;..char|
|00005240| 20 2a 70 61 74 73 61 76 | 65 3b 0a 0a 09 69 66 20 | *patsav|e;...if |
|00005250| 28 20 69 66 6c 61 67 20 | 29 20 7b 09 0a 09 09 69 |( iflag |) {....i|
|00005260| 66 6c 61 67 73 61 76 65 | 20 3d 20 31 3b 0a 09 09 |flagsave| = 1;...|
|00005270| 69 66 6c 61 67 20 3d 20 | 30 3b 0a 09 09 70 61 74 |iflag = |0;...pat|
|00005280| 73 61 76 65 20 3d 20 70 | 61 74 74 65 72 6e 3b 0a |save = p|attern;.|
|00005290| 09 09 70 61 74 74 65 72 | 6e 20 3d 20 73 79 73 35 |..patter|n = sys5|
|000052a0| 66 6f 6c 64 20 28 20 70 | 61 74 74 65 72 6e 20 29 |fold ( p|attern )|
|000052b0| 3b 09 09 2f 2a 20 75 6e | 63 72 69 70 70 6c 65 20 |;../* un|cripple |
|000052c0| 2d 69 20 2a 2f 0a 09 7d | 0a 23 65 6e 64 69 66 0a |-i */..}|.#endif.|
|000052d0| 09 2f 2a 0a 09 20 20 20 | 20 2d 6c 20 76 69 61 20 |./*.. | -l via |
|000052e0| 2d 63 20 69 73 20 73 6e | 65 61 6b 79 2c 20 62 75 |-c is sn|eaky, bu|
|000052f0| 74 20 77 65 27 72 65 20 | 73 68 6f 72 74 20 61 20 |t we're |short a |
|00005300| 67 6f 6f 64 20 70 72 77 | 6f 70 65 6e 28 29 20 0a |good prw|open() .|
|00005310| 09 2a 2f 0a 09 69 66 20 | 28 20 6c 66 6c 61 67 20 |.*/..if |( lflag |
|00005320| 26 26 20 21 63 66 6c 61 | 67 20 29 0a 09 09 73 70 |&& !cfla|g )...sp|
|00005330| 72 69 6e 74 66 20 28 20 | 67 72 65 70 63 6d 64 2c |rintf ( |grepcmd,|
|00005340| 20 22 25 73 20 2d 63 20 | 25 73 20 27 25 73 27 20 | "%s -c |%s '%s' |
|00005350| 7c 20 73 65 64 20 2d 6e | 20 27 2f 5e 30 24 2f 21 || sed -n| '/^0$/!|
|00005360| 73 7c 2e 2a 7c 25 73 7c | 70 27 22 2c 0a 09 09 09 |s|.*|%s||p'",....|
|00005370| 20 20 20 20 20 20 20 20 | 20 20 20 20 45 47 52 45 | | EGRE|
|00005380| 50 2c 20 28 69 66 6c 61 | 67 20 3f 20 22 2d 69 22 |P, (ifla|g ? "-i"|
|00005390| 20 3a 20 22 20 22 29 2c | 20 70 61 74 74 65 72 6e | : " "),| pattern|
|000053a0| 2c 20 66 69 6c 65 20 29 | 3b 0a 09 65 6c 73 65 20 |, file )|;..else |
|000053b0| 69 66 20 28 20 6e 66 69 | 6c 65 20 3c 3d 20 31 20 |if ( nfi|le <= 1 |
|000053c0| 29 0a 09 09 73 70 72 69 | 6e 74 66 20 28 20 67 72 |)...spri|ntf ( gr|
|000053d0| 65 70 63 6d 64 2c 20 22 | 25 73 20 25 73 20 25 73 |epcmd, "|%s %s %s|
|000053e0| 20 27 25 73 27 22 2c 20 | 45 47 52 45 50 2c 0a 09 | '%s'", |EGREP,..|
|000053f0| 09 09 09 20 20 20 20 28 | 63 66 6c 61 67 20 3f 20 |... (|cflag ? |
|00005400| 22 2d 63 22 20 3a 20 22 | 20 22 29 2c 20 28 69 66 |"-c" : "| "), (if|
|00005410| 6c 61 67 20 3f 20 22 2d | 69 22 20 3a 20 22 20 22 |lag ? "-|i" : " "|
|00005420| 29 2c 20 70 61 74 74 65 | 72 6e 20 29 3b 0a 09 65 |), patte|rn );..e|
|00005430| 6c 73 65 0a 09 09 73 70 | 72 69 6e 74 66 20 28 20 |lse...sp|rintf ( |
|00005440| 67 72 65 70 63 6d 64 2c | 20 22 25 73 20 25 73 20 |grepcmd,| "%s %s |
|00005450| 25 73 20 27 25 73 27 20 | 7c 20 73 65 64 20 2d 6e |%s '%s' || sed -n|
|00005460| 20 27 73 7c 5e 7c 25 73 | 3a 7c 70 27 22 2c 20 45 | 's|^|%s|:|p'", E|
|00005470| 47 52 45 50 2c 0a 09 09 | 09 09 20 20 20 20 28 63 |GREP,...|.. (c|
|00005480| 66 6c 61 67 20 3f 20 22 | 2d 63 22 20 3a 20 22 20 |flag ? "|-c" : " |
|00005490| 22 29 2c 20 28 69 66 6c | 61 67 20 3f 20 22 2d 69 |"), (ifl|ag ? "-i|
|000054a0| 22 20 3a 20 22 20 22 29 | 2c 20 70 61 74 74 65 72 |" : " ")|, patter|
|000054b0| 6e 2c 20 66 69 6c 65 20 | 29 3b 0a 09 2f 2a 0a 09 |n, file |);../*..|
|000054c0| 20 20 20 20 77 65 20 74 | 68 61 6e 6b 20 6d 72 2e | we t|hank mr.|
|000054d0| 20 74 68 6f 6d 70 73 6f | 6e 20 66 6f 72 20 61 6e | thompso|n for an|
|000054e0| 20 65 73 70 65 63 69 61 | 6c 20 6e 64 66 61 20 73 | especia|l ndfa s|
|000054f0| 69 6d 75 6c 61 74 69 6f | 6e 2e 0a 09 20 20 20 20 |imulatio|n... |
|00005500| 28 63 6f 6e 73 75 6c 74 | 20 63 61 63 6d 2c 20 6a |(consult| cacm, j|
|00005510| 75 6e 65 20 31 39 36 38 | 2c 20 6f 72 20 61 68 6f |une 1968|, or aho|
|00005520| 20 65 74 2e 20 61 6c 2e | 2c 20 64 65 73 69 67 6e | et. al.|, design|
|00005530| 20 26 20 61 6e 61 6c 79 | 73 69 73 20 2e 2e 2e 2c | & analy|sis ...,|
|00005540| 0a 09 20 20 20 20 61 6c | 67 6f 72 69 74 68 6d 20 |.. al|gorithm |
|00005550| 39 2e 31 29 2e 0a 09 2a | 2f 0a 23 69 66 64 65 66 |9.1)...*|/.#ifdef|
|00005560| 20 42 53 44 0a 09 69 66 | 20 28 20 69 66 6c 61 67 | BSD..if| ( iflag|
|00005570| 73 61 76 65 20 29 20 7b | 0a 09 09 69 66 6c 61 67 |save ) {|...iflag|
|00005580| 20 3d 20 31 3b 0a 09 09 | 70 61 74 74 65 72 6e 20 | = 1;...|pattern |
|00005590| 3d 20 70 61 74 73 61 76 | 65 3b 0a 09 7d 0a 23 65 |= patsav|e;..}.#e|
|000055a0| 6e 64 69 66 0a 09 72 65 | 74 75 72 6e 20 28 20 70 |ndif..re|turn ( p|
|000055b0| 6f 70 65 6e 20 28 20 67 | 72 65 70 63 6d 64 2c 20 |open ( g|repcmd, |
|000055c0| 22 77 22 20 29 20 29 3b | 0a 7d 0a 0a 67 6f 73 70 |"w" ) );|.}..gosp|
|000055d0| 65 72 20 28 20 70 61 74 | 74 65 72 6e 20 29 09 09 |er ( pat|tern )..|
|000055e0| 2f 2a 20 63 6f 6d 70 75 | 74 65 20 22 62 6f 79 65 |/* compu|te "boye|
|000055f0| 72 2d 6d 6f 6f 72 65 22 | 20 64 65 6c 74 61 20 74 |r-moore"| delta t|
|00005600| 61 62 6c 65 20 2a 2f 0a | 09 63 68 61 72 20 2a 70 |able */.|.char *p|
|00005610| 61 74 74 65 72 6e 3b 09 | 09 2f 2a 20 2e 2e 2e 20 |attern;.|./* ... |
|00005620| 48 41 4b 4d 45 4d 20 6c | 69 76 65 73 20 2e 2e 2e |HAKMEM l|ives ...|
|00005630| 20 2a 2f 0a 7b 0a 09 72 | 65 67 69 73 74 65 72 20 | */.{..r|egister |
|00005640| 69 6e 74 20 6a 2c 20 70 | 61 74 6c 65 6e 3b 0a 09 |int j, p|atlen;..|
|00005650| 2f 2a 0a 09 20 20 20 20 | 66 6f 72 20 6d 75 6c 74 |/*.. |for mult|
|00005660| 69 62 79 74 65 20 63 68 | 61 72 61 63 74 65 72 73 |ibyte ch|aracters|
|00005670| 20 28 65 2e 67 2e 20 6b | 61 6e 6a 69 29 2c 20 74 | (e.g. k|anji), t|
|00005680| 68 65 72 65 20 61 72 65 | 20 77 61 79 73 2e 0a 09 |here are| ways...|
|00005690| 20 20 20 20 65 78 74 72 | 61 70 6f 6c 61 74 69 6e | extr|apolatin|
|000056a0| 67 20 32 35 36 20 74 6f | 20 36 34 4b 20 6d 61 79 |g 256 to| 64K may|
|000056b0| 20 62 65 20 75 6e 77 69 | 73 65 2c 20 69 6e 20 66 | be unwi|se, in f|
|000056c0| 61 76 6f 72 20 6f 66 20 | 6d 6f 72 65 0a 09 20 20 |avor of |more.. |
|000056d0| 20 20 64 79 6e 61 6d 69 | 63 73 20 77 69 74 68 69 | dynami|cs withi|
|000056e0| 6e 20 62 6f 79 65 72 6d | 6f 6f 72 65 28 29 20 69 |n boyerm|oore() i|
|000056f0| 74 73 65 6c 66 2e 20 0a | 09 2a 2f 0a 09 70 61 74 |tself. .|.*/..pat|
|00005700| 6c 65 6e 20 3d 20 73 74 | 72 6c 65 6e 20 28 20 70 |len = st|rlen ( p|
|00005710| 61 74 74 65 72 6e 20 29 | 3b 0a 0a 09 66 6f 72 20 |attern )|;...for |
|00005720| 28 20 6a 20 3d 20 30 3b | 20 6a 20 3c 20 32 35 36 |( j = 0;| j < 256|
|00005730| 3b 20 6a 2b 2b 20 29 20 | 7b 0a 09 09 64 65 6c 74 |; j++ ) |{...delt|
|00005740| 61 30 5b 6a 5d 20 3d 20 | 70 61 74 6c 65 6e 3b 0a |a0[j] = |patlen;.|
|00005750| 09 09 63 6d 61 70 5b 6a | 5d 20 3d 20 28 63 68 61 |..cmap[j|] = (cha|
|00005760| 72 29 20 6a 3b 09 2f 2a | 20 63 6f 75 6c 64 20 62 |r) j;./*| could b|
|00005770| 65 20 64 6f 6e 65 20 61 | 74 20 63 6f 6d 70 69 6c |e done a|t compil|
|00005780| 65 20 74 69 6d 65 20 2a | 2f 0a 09 7d 0a 09 66 6f |e time *|/..}..fo|
|00005790| 72 20 28 20 6a 20 3d 20 | 30 3b 20 6a 20 3c 20 70 |r ( j = |0; j < p|
|000057a0| 61 74 6c 65 6e 20 2d 20 | 31 3b 20 6a 2b 2b 20 29 |atlen - |1; j++ )|
|000057b0| 0a 09 09 64 65 6c 74 61 | 30 5b 70 61 74 74 65 72 |...delta|0[patter|
|000057c0| 6e 5b 6a 5d 5d 20 3d 20 | 70 61 74 6c 65 6e 20 2d |n[j]] = |patlen -|
|000057d0| 20 6a 20 2d 20 31 3b 0a | 09 64 65 6c 74 61 30 5b | j - 1;.|.delta0[|
|000057e0| 70 61 74 74 65 72 6e 5b | 70 61 74 6c 65 6e 20 2d |pattern[|patlen -|
|000057f0| 20 31 5d 5d 20 3d 20 4c | 41 52 47 45 3b 0a 0a 09 | 1]] = L|ARGE;...|
|00005800| 69 66 20 28 20 69 66 6c | 61 67 20 29 20 7b 0a 09 |if ( ifl|ag ) {..|
|00005810| 09 66 6f 72 20 28 20 6a | 20 3d 20 30 3b 20 6a 20 |.for ( j| = 0; j |
|00005820| 3c 20 70 61 74 6c 65 6e | 20 2d 20 31 3b 20 6a 2b |< patlen| - 1; j+|
|00005830| 2b 20 29 0a 09 09 09 69 | 66 20 28 20 69 73 6c 6f |+ )....i|f ( islo|
|00005840| 77 65 72 20 28 20 28 69 | 6e 74 29 20 70 61 74 74 |wer ( (i|nt) patt|
|00005850| 65 72 6e 5b 6a 5d 20 29 | 20 29 0a 09 09 09 09 64 |ern[j] )| ).....d|
|00005860| 65 6c 74 61 30 5b 74 6f | 75 70 70 65 72 20 28 28 |elta0[to|upper ((|
|00005870| 69 6e 74 29 20 70 61 74 | 74 65 72 6e 5b 6a 5d 29 |int) pat|tern[j])|
|00005880| 5d 20 3d 20 70 61 74 6c | 65 6e 20 2d 20 6a 20 2d |] = patl|en - j -|
|00005890| 20 31 3b 0a 09 09 69 66 | 20 28 20 69 73 6c 6f 77 | 1;...if| ( islow|
|000058a0| 65 72 20 28 20 28 69 6e | 74 29 20 70 61 74 74 65 |er ( (in|t) patte|
|000058b0| 72 6e 5b 70 61 74 6c 65 | 6e 20 2d 20 31 5d 20 29 |rn[patle|n - 1] )|
|000058c0| 20 29 0a 09 09 09 64 65 | 6c 74 61 30 5b 74 6f 75 | )....de|lta0[tou|
|000058d0| 70 70 65 72 20 28 28 69 | 6e 74 29 20 70 61 74 74 |pper ((i|nt) patt|
|000058e0| 65 72 6e 5b 70 61 74 6c | 65 6e 20 2d 20 31 5d 29 |ern[patl|en - 1])|
|000058f0| 5d 20 3d 20 4c 41 52 47 | 45 3b 0a 09 09 66 6f 72 |] = LARG|E;...for|
|00005900| 20 28 20 6a 20 3d 20 27 | 41 27 3b 20 6a 20 3c 3d | ( j = '|A'; j <=|
|00005910| 20 27 5a 27 3b 20 6a 2b | 2b 20 29 0a 09 09 09 63 | 'Z'; j+|+ )....c|
|00005920| 6d 61 70 5b 6a 5d 20 3d | 20 28 63 68 61 72 29 20 |map[j] =| (char) |
|00005930| 74 6f 6c 6f 77 65 72 20 | 28 20 28 69 6e 74 29 20 |tolower |( (int) |
|00005940| 6a 20 29 3b 0a 09 7d 0a | 7d 0a 0a 63 68 61 72 20 |j );..}.|}..char |
|00005950| 2a 0a 67 6f 74 61 6d 61 | 74 63 68 20 28 20 66 69 |*.gotama|tch ( fi|
|00005960| 6c 65 2c 20 73 20 29 09 | 09 2f 2a 20 70 72 69 6e |le, s ).|./* prin|
|00005970| 74 2c 20 63 6f 75 6e 74 | 2c 20 6f 72 20 73 74 6f |t, count|, or sto|
|00005980| 70 20 6f 6e 20 66 75 6c | 6c 20 6d 61 74 63 68 20 |p on ful|l match |
|00005990| 2a 2f 0a 09 72 65 67 69 | 73 74 65 72 20 63 68 61 |*/..regi|ster cha|
|000059a0| 72 20 2a 66 69 6c 65 2c | 20 2a 73 3b 0a 7b 0a 09 |r *file,| *s;.{..|
|000059b0| 6e 73 75 63 63 65 73 73 | 20 3d 20 31 3b 0a 09 69 |nsuccess| = 1;..i|
|000059c0| 66 20 28 20 63 66 6c 61 | 67 20 29 20 7b 09 09 2f |f ( cfla|g ) {../|
|000059d0| 2a 20 2d 63 20 6f 76 65 | 72 72 69 64 65 73 20 2d |* -c ove|rrides -|
|000059e0| 6c 2c 20 66 6f 72 20 73 | 6f 6d 65 20 72 65 61 73 |l, for s|ome reas|
|000059f0| 6f 6e 20 2a 2f 0a 09 09 | 6e 6d 61 74 63 68 2b 2b |on */...|nmatch++|
|00005a00| 3b 0a 09 09 64 6f 0a 09 | 09 09 3b 0a 09 09 77 68 |;...do..|..;...wh|
|00005a10| 69 6c 65 20 28 20 2a 73 | 2b 2b 20 21 3d 20 4e 4c |ile ( *s|++ != NL|
|00005a20| 20 29 3b 0a 09 7d 0a 09 | 65 6c 73 65 20 69 66 20 | );..}..|else if |
|00005a30| 28 20 6c 66 6c 61 67 20 | 29 20 7b 0a 09 09 70 75 |( lflag |) {...pu|
|00005a40| 74 73 20 28 20 66 69 6c | 65 20 29 3b 0a 09 09 72 |ts ( fil|e );...r|
|00005a50| 65 74 75 72 6e 20 28 20 | 4e 55 4c 4c 20 29 3b 0a |eturn ( |NULL );.|
|00005a60| 09 7d 0a 09 65 6c 73 65 | 20 7b 0a 09 09 69 66 20 |.}..else| {...if |
|00005a70| 28 20 6e 66 69 6c 65 20 | 3e 20 31 20 29 0a 09 09 |( nfile |> 1 )...|
|00005a80| 09 70 72 69 6e 74 66 20 | 28 20 22 25 73 3a 22 2c |.printf |( "%s:",|
|00005a90| 20 66 69 6c 65 20 29 3b | 0a 09 09 64 6f 0a 09 09 | file );|...do...|
|00005aa0| 09 70 75 74 63 68 61 72 | 20 28 20 2a 73 20 29 3b |.putchar| ( *s );|
|00005ab0| 0a 09 09 77 68 69 6c 65 | 20 28 20 2a 73 2b 2b 20 |...while| ( *s++ |
|00005ac0| 21 3d 20 4e 4c 20 29 3b | 0a 09 7d 0a 09 72 65 74 |!= NL );|..}..ret|
|00005ad0| 75 72 6e 20 28 20 28 68 | 66 6c 61 67 20 26 26 20 |urn ( (h|flag && |
|00005ae0| 21 63 66 6c 61 67 29 20 | 3f 20 4e 55 4c 4c 20 3a |!cflag) |? NULL :|
|00005af0| 20 73 20 29 3b 0a 7d 0a | 0a 0a 63 68 61 72 20 2a | s );.}.|..char *|
|00005b00| 0a 66 6f 6c 64 20 28 20 | 6c 69 6e 65 20 29 0a 09 |.fold ( |line )..|
|00005b10| 63 68 61 72 20 2a 6c 69 | 6e 65 3b 0a 7b 0a 09 73 |char *li|ne;.{..s|
|00005b20| 74 61 74 69 63 20 63 68 | 61 72 20 66 6c 69 6e 65 |tatic ch|ar fline|
|00005b30| 5b 42 55 46 53 49 5a 45 | 5d 3b 0a 09 72 65 67 69 |[BUFSIZE|];..regi|
|00005b40| 73 74 65 72 20 63 68 61 | 72 20 2a 73 2c 20 2a 74 |ster cha|r *s, *t|
|00005b50| 20 3d 20 66 6c 69 6e 65 | 3b 0a 0a 09 66 6f 72 20 | = fline|;...for |
|00005b60| 28 20 73 20 3d 20 6c 69 | 6e 65 3b 20 2a 73 20 21 |( s = li|ne; *s !|
|00005b70| 3d 20 45 4f 53 3b 20 73 | 2b 2b 20 29 0a 09 09 2a |= EOS; s|++ )...*|
|00005b80| 74 2b 2b 20 3d 20 28 69 | 73 75 70 70 65 72 20 28 |t++ = (i|supper (|
|00005b90| 28 69 6e 74 29 20 2a 73 | 29 20 3f 20 28 63 68 61 |(int) *s|) ? (cha|
|00005ba0| 72 29 20 74 6f 6c 6f 77 | 65 72 20 28 28 69 6e 74 |r) tolow|er ((int|
|00005bb0| 29 20 2a 73 29 20 3a 20 | 2a 73 20 29 3b 0a 09 2a |) *s) : |*s );..*|
|00005bc0| 74 20 3d 20 45 4f 53 3b | 0a 09 72 65 74 75 72 6e |t = EOS;|..return|
|00005bd0| 20 28 20 66 6c 69 6e 65 | 20 29 3b 0a 7d 0a 09 0a | ( fline| );.}...|
|00005be0| 23 69 66 64 65 66 20 42 | 53 44 0a 63 68 61 72 20 |#ifdef B|SD.char |
|00005bf0| 2a 0a 73 79 73 35 66 6f | 6c 64 20 28 20 6c 69 6e |*.sys5fo|ld ( lin|
|00005c00| 65 20 29 09 2f 2a 20 61 | 20 77 6f 72 6b 61 72 6f |e )./* a| workaro|
|00005c10| 75 6e 64 20 6b 6c 75 64 | 67 65 20 66 6f 72 20 74 |und klud|ge for t|
|00005c20| 68 65 20 6f 6c 64 20 61 | 6c 6d 61 20 6d 61 74 65 |he old a|lma mate|
|00005c30| 72 2c 20 65 2e 67 2e 20 | 2a 2f 0a 09 63 68 61 72 |r, e.g. |*/..char|
|00005c40| 20 2a 6c 69 6e 65 3b 09 | 2f 2a 20 2e 2e 2e 20 22 | *line;.|/* ... "|
|00005c50| 5a 49 50 2e 2a 50 59 22 | 20 62 65 63 6f 6d 65 73 |ZIP.*PY"| becomes|
|00005c60| 20 22 5b 7a 5a 5d 5b 69 | 49 5d 5b 70 50 5d 2e 2a | "[zZ][i|I][pP].*|
|00005c70| 5b 70 50 5d 5b 79 59 5d | 22 20 2a 2f 0a 7b 0a 09 |[pP][yY]|" */.{..|
|00005c80| 72 65 67 69 73 74 65 72 | 20 63 68 61 72 20 2a 70 |register| char *p|
|00005c90| 2c 20 2a 73 3b 0a 09 73 | 74 61 74 69 63 20 63 68 |, *s;..s|tatic ch|
|00005ca0| 61 72 20 70 6c 69 6e 65 | 5b 42 55 46 53 49 5a 45 |ar pline|[BUFSIZE|
|00005cb0| 5d 3b 0a 09 63 68 61 72 | 20 63 2c 20 73 74 65 6e |];..char| c, sten|
|00005cc0| 63 69 6c 5b 35 5d 3b 0a | 09 69 6e 74 20 62 64 61 |cil[5];.|.int bda|
|00005cd0| 6e 67 65 72 20 3d 20 30 | 3b 0a 0a 09 70 6c 69 6e |nger = 0|;...plin|
|00005ce0| 65 5b 30 5d 20 3d 20 45 | 4f 53 3b 0a 09 66 6f 72 |e[0] = E|OS;..for|
|00005cf0| 20 28 20 73 20 3d 20 6c | 69 6e 65 3b 20 2a 73 20 | ( s = l|ine; *s |
|00005d00| 21 3d 20 45 4f 53 3b 20 | 73 2b 2b 20 29 20 7b 0a |!= EOS; |s++ ) {.|
|00005d10| 09 09 69 66 20 28 20 2a | 73 20 3d 3d 20 27 5b 27 |..if ( *|s == '['|
|00005d20| 20 29 0a 09 09 09 62 64 | 61 6e 67 65 72 20 3d 20 | )....bd|anger = |
|00005d30| 31 3b 0a 09 09 69 66 20 | 28 20 62 64 61 6e 67 65 |1;...if |( bdange|
|00005d40| 72 20 3d 3d 20 31 20 26 | 26 20 2a 73 20 3d 3d 20 |r == 1 &|& *s == |
|00005d50| 27 5d 27 20 29 0a 09 09 | 09 62 64 61 6e 67 65 72 |']' )...|.bdanger|
|00005d60| 20 3d 20 30 3b 0a 09 09 | 69 66 20 28 20 69 73 61 | = 0;...|if ( isa|
|00005d70| 6c 70 68 61 20 28 20 28 | 69 6e 74 29 20 2a 73 20 |lpha ( (|int) *s |
|00005d80| 29 20 29 20 7b 0a 09 09 | 09 63 20 3d 20 28 20 28 |) ) {...|.c = ( (|
|00005d90| 69 73 6c 6f 77 65 72 20 | 28 20 2a 73 20 29 29 20 |islower |( *s )) |
|00005da0| 3f 20 28 63 68 61 72 29 | 20 74 6f 75 70 70 65 72 |? (char)| toupper|
|00005db0| 20 28 20 28 69 6e 74 29 | 20 2a 73 20 29 20 3a 0a | ( (int)| *s ) :.|
|00005dc0| 09 09 09 09 09 09 20 28 | 63 68 61 72 29 20 74 6f |...... (|char) to|
|00005dd0| 6c 6f 77 65 72 20 28 20 | 28 69 6e 74 29 20 2a 73 |lower ( |(int) *s|
|00005de0| 20 29 20 29 3b 0a 09 09 | 09 73 70 72 69 6e 74 66 | ) );...|.sprintf|
|00005df0| 20 28 20 73 74 65 6e 63 | 69 6c 2c 20 28 28 62 64 | ( stenc|il, ((bd|
|00005e00| 61 6e 67 65 72 29 20 3f | 20 22 25 63 25 63 22 20 |anger) ?| "%c%c" |
|00005e10| 3a 20 22 5b 25 63 25 63 | 5d 22 29 2c 20 2a 73 2c |: "[%c%c|]"), *s,|
|00005e20| 20 63 20 29 3b 20 0a 09 | 09 7d 0a 09 09 65 6c 73 | c ); ..|.}...els|
|00005e30| 65 20 7b 0a 09 09 09 73 | 74 65 6e 63 69 6c 5b 30 |e {....s|tencil[0|
|00005e40| 5d 20 3d 20 2a 73 3b 0a | 09 09 09 73 74 65 6e 63 |] = *s;.|...stenc|
|00005e50| 69 6c 5b 31 5d 20 3d 20 | 45 4f 53 3b 0a 09 09 7d |il[1] = |EOS;...}|
|00005e60| 0a 09 09 73 74 72 63 61 | 74 20 28 20 70 6c 69 6e |...strca|t ( plin|
|00005e70| 65 2c 20 73 74 65 6e 63 | 69 6c 20 29 3b 0a 09 7d |e, stenc|il );..}|
|00005e80| 0a 09 2a 73 20 3d 20 45 | 4f 53 3b 0a 09 72 65 74 |..*s = E|OS;..ret|
|00005e90| 75 72 6e 20 28 20 70 6c | 69 6e 65 20 29 3b 0a 7d |urn ( pl|ine );.}|
|00005ea0| 0a 23 65 6e 64 69 66 0a | 0a 6f 6f 70 73 20 28 20 |.#endif.|.oops ( |
|00005eb0| 6d 65 73 73 61 67 65 20 | 29 20 0a 09 63 68 61 72 |message |) ..char|
|00005ec0| 20 2a 6d 65 73 73 61 67 | 65 3b 0a 7b 0a 09 66 70 | *messag|e;.{..fp|
|00005ed0| 72 69 6e 74 66 20 28 20 | 73 74 64 65 72 72 2c 20 |rintf ( |stderr, |
|00005ee0| 22 25 73 5c 6e 22 2c 20 | 6d 65 73 73 61 67 65 20 |"%s\n", |message |
|00005ef0| 29 3b 0a 09 65 78 69 74 | 20 28 20 32 20 29 3b 0a |);..exit| ( 2 );.|
|00005f00| 7d 0a 53 48 41 52 5f 45 | 4f 46 0a 69 66 20 74 65 |}.SHAR_E|OF.if te|
|00005f10| 73 74 20 31 31 32 31 39 | 20 2d 6e 65 20 22 60 77 |st 11219| -ne "`w|
|00005f20| 63 20 2d 63 20 3c 20 27 | 65 67 72 65 70 2e 63 27 |c -c < '|egrep.c'|
|00005f30| 60 22 0a 74 68 65 6e 0a | 09 65 63 68 6f 20 73 68 |`".then.|.echo sh|
|00005f40| 61 72 3a 20 65 72 72 6f | 72 20 74 72 61 6e 73 6d |ar: erro|r transm|
|00005f50| 69 74 74 69 6e 67 20 22 | 27 65 67 72 65 70 2e 63 |itting "|'egrep.c|
|00005f60| 27 22 20 27 28 73 68 6f | 75 6c 64 20 68 61 76 65 |'" '(sho|uld have|
|00005f70| 20 62 65 65 6e 20 31 31 | 32 31 39 20 63 68 61 72 | been 11|219 char|
|00005f80| 61 63 74 65 72 73 29 27 | 0a 66 69 0a 66 69 0a 65 |acters)'|.fi.fi.e|
|00005f90| 63 68 6f 20 73 68 61 72 | 3a 20 65 78 74 72 61 63 |cho shar|: extrac|
|00005fa0| 74 69 6e 67 20 22 27 63 | 6f 6d 70 61 74 2d 73 79 |ting "'c|ompat-sy|
|00005fb0| 73 35 2e 63 27 22 20 27 | 28 32 36 34 35 20 63 68 |s5.c'" '|(2645 ch|
|00005fc0| 61 72 61 63 74 65 72 73 | 29 27 0a 69 66 20 74 65 |aracters|)'.if te|
|00005fd0| 73 74 20 2d 66 20 27 63 | 6f 6d 70 61 74 2d 73 79 |st -f 'c|ompat-sy|
|00005fe0| 73 35 2e 63 27 0a 74 68 | 65 6e 0a 09 65 63 68 6f |s5.c'.th|en..echo|
|00005ff0| 20 73 68 61 72 3a 20 77 | 69 6c 6c 20 6e 6f 74 20 | shar: w|ill not |
|00006000| 6f 76 65 72 2d 77 72 69 | 74 65 20 65 78 69 73 74 |over-wri|te exist|
|00006010| 69 6e 67 20 66 69 6c 65 | 20 22 27 63 6f 6d 70 61 |ing file| "'compa|
|00006020| 74 2d 73 79 73 35 2e 63 | 27 22 0a 65 6c 73 65 0a |t-sys5.c|'".else.|
|00006030| 63 61 74 20 3c 3c 20 5c | 53 48 41 52 5f 45 4f 46 |cat << \|SHAR_EOF|
|00006040| 20 3e 20 27 63 6f 6d 70 | 61 74 2d 73 79 73 35 2e | > 'comp|at-sys5.|
|00006050| 63 27 0a 2f 2a 0a 20 2a | 20 72 65 67 63 6f 6d 70 |c'./*. *| regcomp|
|00006060| 28 29 2c 20 72 65 67 65 | 78 65 63 28 29 2c 20 61 |(), rege|xec(), a|
|00006070| 6e 64 20 78 72 65 61 64 | 28 29 20 77 65 72 65 20 |nd xread|() were |
|00006080| 70 6f 73 74 65 64 20 74 | 6f 20 6d 6f 64 2e 73 6f |posted t|o mod.so|
|00006090| 75 72 63 65 73 20 62 79 | 0a 20 2a 20 68 65 6e 72 |urces by|. * henr|
|000060a0| 79 20 73 70 65 6e 63 65 | 72 2c 20 61 6e 64 20 61 |y spence|r, and a|
|000060b0| 72 65 20 74 6f 6f 20 6c | 61 72 67 65 20 74 6f 20 |re too l|arge to |
|000060c0| 62 65 20 69 6e 63 6c 75 | 64 65 64 20 68 65 72 65 |be inclu|ded here|
|000060d0| 2e 0a 20 2a 0a 20 2a 20 | 54 68 69 73 20 66 69 6c |.. *. * |This fil|
|000060e0| 65 20 63 6f 6e 74 61 69 | 6e 73 20 73 74 72 63 73 |e contai|ns strcs|
|000060f0| 70 6e 2c 20 73 74 72 63 | 68 72 2c 20 73 74 72 70 |pn, strc|hr, strp|
|00006100| 62 72 6b 2c 20 61 6e 64 | 20 67 65 74 6f 70 74 2e |brk, and| getopt.|
|00006110| 0a 20 2a 2f 0a 0a 23 69 | 6e 63 6c 75 64 65 20 3c |. */..#i|nclude <|
|00006120| 73 74 64 69 6f 2e 68 3e | 0a 2f 2a 0a 20 2a 20 73 |stdio.h>|./*. * s|
|00006130| 74 72 63 73 70 6e 20 2d | 20 66 69 6e 64 20 6c 65 |trcspn -| find le|
|00006140| 6e 67 74 68 20 6f 66 20 | 69 6e 69 74 69 61 6c 20 |ngth of |initial |
|00006150| 73 65 67 6d 65 6e 74 20 | 6f 66 20 73 31 20 63 6f |segment |of s1 co|
|00006160| 6e 73 69 73 74 69 6e 67 | 20 65 6e 74 69 72 65 6c |nsisting| entirel|
|00006170| 79 0a 20 2a 20 6f 66 20 | 63 68 61 72 61 63 74 65 |y. * of |characte|
|00006180| 72 73 20 6e 6f 74 20 66 | 72 6f 6d 20 73 32 0a 20 |rs not f|rom s2. |
|00006190| 2a 2f 0a 0a 69 6e 74 20 | 73 74 72 63 73 70 6e 28 |*/..int |strcspn(|
|000061a0| 73 31 2c 20 73 32 29 0a | 63 68 61 72 20 2a 73 31 |s1, s2).|char *s1|
|000061b0| 3b 0a 63 68 61 72 20 2a | 73 32 3b 0a 7b 0a 09 72 |;.char *|s2;.{..r|
|000061c0| 65 67 69 73 74 65 72 20 | 63 68 61 72 20 2a 73 63 |egister |char *sc|
|000061d0| 61 6e 31 3b 0a 09 72 65 | 67 69 73 74 65 72 20 63 |an1;..re|gister c|
|000061e0| 68 61 72 20 2a 73 63 61 | 6e 32 3b 0a 09 72 65 67 |har *sca|n2;..reg|
|000061f0| 69 73 74 65 72 20 69 6e | 74 20 63 6f 75 6e 74 3b |ister in|t count;|
|00006200| 0a 0a 09 63 6f 75 6e 74 | 20 3d 20 30 3b 0a 09 66 |...count| = 0;..f|
|00006210| 6f 72 20 28 73 63 61 6e | 31 20 3d 20 73 31 3b 20 |or (scan|1 = s1; |
|00006220| 2a 73 63 61 6e 31 20 21 | 3d 20 27 5c 30 27 3b 20 |*scan1 !|= '\0'; |
|00006230| 73 63 61 6e 31 2b 2b 29 | 20 7b 0a 09 09 66 6f 72 |scan1++)| {...for|
|00006240| 20 28 73 63 61 6e 32 20 | 3d 20 73 32 3b 20 2a 73 | (scan2 |= s2; *s|
|00006250| 63 61 6e 32 20 21 3d 20 | 27 5c 30 27 3b 29 09 2f |can2 != |'\0';)./|
|00006260| 2a 20 2b 2b 20 6d 6f 76 | 65 64 20 64 6f 77 6e 2e |* ++ mov|ed down.|
|00006270| 20 2a 2f 0a 09 09 09 69 | 66 20 28 2a 73 63 61 6e | */....i|f (*scan|
|00006280| 31 20 3d 3d 20 2a 73 63 | 61 6e 32 2b 2b 29 0a 09 |1 == *sc|an2++)..|
|00006290| 09 09 09 72 65 74 75 72 | 6e 28 63 6f 75 6e 74 29 |...retur|n(count)|
|000062a0| 3b 0a 09 09 63 6f 75 6e | 74 2b 2b 3b 0a 09 7d 0a |;...coun|t++;..}.|
|000062b0| 09 72 65 74 75 72 6e 28 | 63 6f 75 6e 74 29 3b 0a |.return(|count);.|
|000062c0| 7d 0a 0a 63 68 61 72 20 | 2a 73 74 72 63 68 72 28 |}..char |*strchr(|
|000062d0| 61 2c 20 62 29 0a 63 68 | 61 72 20 2a 61 2c 20 62 |a, b).ch|ar *a, b|
|000062e0| 3b 0a 20 20 20 20 7b 0a | 20 20 20 20 63 68 61 72 |;. {.| char|
|000062f0| 20 2a 69 6e 64 65 78 28 | 29 3b 0a 20 20 20 20 72 | *index(|);. r|
|00006300| 65 74 75 72 6e 20 28 69 | 6e 64 65 78 28 61 2c 20 |eturn (i|ndex(a, |
|00006310| 62 29 29 3b 0a 20 20 20 | 20 7d 0a 0a 2f 2a 20 73 |b));. | }../* s|
|00006320| 74 72 70 62 72 6b 20 2d | 20 52 65 74 75 72 6e 73 |trpbrk -| Returns|
|00006330| 20 61 20 70 6f 69 6e 74 | 65 72 20 74 6f 20 74 68 | a point|er to th|
|00006340| 65 20 66 69 72 73 74 20 | 63 68 61 72 61 63 74 65 |e first |characte|
|00006350| 72 20 6f 66 20 73 6f 75 | 72 63 65 20 74 68 61 74 |r of sou|rce that|
|00006360| 20 69 73 20 61 6e 79 0a | 20 2a 20 20 6f 66 20 74 | is any.| * of t|
|00006370| 68 65 20 73 70 65 63 69 | 66 69 65 64 20 6b 65 79 |he speci|fied key|
|00006380| 73 2c 20 6f 72 20 4e 55 | 4c 4c 20 69 66 20 6e 6f |s, or NU|LL if no|
|00006390| 6e 65 20 6f 66 20 74 68 | 65 20 6b 65 79 73 20 61 |ne of th|e keys a|
|000063a0| 72 65 20 70 72 65 73 65 | 6e 74 0a 20 2a 20 20 69 |re prese|nt. * i|
|000063b0| 6e 20 74 68 65 20 73 6f | 75 72 63 65 20 73 74 72 |n the so|urce str|
|000063c0| 69 6e 67 2e 0a 20 2a 2f | 0a 63 68 61 72 20 2a 73 |ing.. */|.char *s|
|000063d0| 74 72 70 62 72 6b 28 73 | 6f 75 72 63 65 2c 20 6b |trpbrk(s|ource, k|
|000063e0| 65 79 73 29 0a 63 68 61 | 72 20 2a 73 6f 75 72 63 |eys).cha|r *sourc|
|000063f0| 65 2c 20 2a 6b 65 79 73 | 3b 0a 7b 0a 20 20 20 20 |e, *keys|;.{. |
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
