Brute force text searching


program wc( input, output ); const MAXPATLEN = 5; const MAXTEXTLEN = 1000; const MAXCHAR = 127; type PATTERN = packed array [1..MAXPATLEN] of char; TEXT = packed array [1..MAXTEXTLEN] of char; var pat: PATTERN; text: TEXT; pos: integer; function search( pat: PATTERN; text: TEXT ): integer; var i, j, k, m, n: integer; skip: array [0..MAXCHAR] of integer; found: boolean; begin found := FALSE; search := 0; m := length(pat); if m=0 then begin search := 1; found := TRUE; end; for k:=0 to MAXCHAR do skip[k] := m; { Preprocessing } for k:=1 to m-1 do skip[ord(pat[k])] := m-k; n := length(text); { Search } writeln( 'pat ', pat, ' text = ', text ); writeln( 'm = ', m, 'n = ', n ); k := m; while not found and (k <= n) do begin i := k; j := m; while (j >= 1) do if text[i] <> pat[j] then j := -1 else begin j := j-1; i := i-1; end; if j = 0 then begin search := i+1; found := TRUE; end; k := k + skip[ord(text[k])]; end; end; begin { while not eof(f) do begin read(pat); read(text); } pos := search('aaaab','aaaa5aaa9aaaab'); writeln( 'pattern found at ', pos ); { end; } end.

Pascal source (713.wc.p)



© Addison-Wesley Publishing Co. Inc.