|
<![CDATA[
program wc( input, output );
const MAXPATLEN = 5;
const MAXTEXTLEN = 1000;
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 next: array [1..MAXPATLEN] of integer;
i, j, m, n: integer;
found: boolean;
procedure preprocpat; {( pat: PATTERN;
var next: array [1..MAXPATLEN] of integer );}
var k, l: integer;
begin
m := length(pat);
l := 1;
k := 0; next[1] := 0;
repeat begin
if (k=0) or (pat[l]=pat[k]) then begin
l := l+1; k := k+1;
if pat[k]=pat[l] then next[l] := next[k]
else next[l] := k;
end
else k := next[k];
end;
until ( l > m );
end;
begin
writeln('pat: ', pat, 'text: ', text );
m := length(pat);
found := FALSE;
if m=0 then begin
search := 1;
found := TRUE;
end;
preprocpat; {( pat, next );}
n := length(text);
writeln( 'm = ', m, 'n = ', n );
j := 1; i := 1;
while not found and (i <= n) do begin
if (j=0) or (pat[j] = text[i]) then begin
i := i+1; j := j+1;
if j > m then begin
search := i-j+1;
found := TRUE;
end;
end
else j := next[j];
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 (712.wc.p) 