Cod sursa(job #298582)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 6 aprilie 2009 11:17:52
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.47 kb
//Arhiva educationala - Potrivirea sirurilor - KMP

type
	string2 = array[1..2000000] of char;
	vect	= array[1..2000000] of longint;
var
	n, m : string2;
	pn : vect;
	pos : array[1..1000] of longint;
	ln, lm, nr, i: longint;
	f : text;
	
function min (a, b : longint) : longint;
begin
if (a < b) then min := a else min := b;
end;

function cBin (var s: string2; lo, hi : longint) : longint;
var
	mi : longint;
begin
while (lo <= hi) do
	begin
	mi := lo + (hi - lo) shr 1;
	if (s[mi] <> #0) then	lo := mi + 1
		else				hi := mi - 1;
	end;
cBin := hi;
end;

procedure prefix (var s : string2; var ps : vect; ls : longint);
var
	k, i : longint;
begin
k := 0;
ps [1] := 0;
for i := 2 to ls do
	begin
	while (k > 0) and (s[k+1] <> s[i]) do
		k := ps[k];
	if (s[k+1] = s[i]) then
		inc (k);
	ps[i] := k;
	end;
end;

procedure KMP;
var
	q, i : longint;
begin
q := 0;
nr := 0;
for i := 1 to lm do
	begin
	while (q > 0) and (n[q + 1] <> m[i]) do
		q := pn[q];
	if (n[q + 1] = m[i]) then
		inc (q);
	if (q = ln) then
        begin
        inc (nr);
		if (nr <= 1000) then
            pos[nr] := i-ln;
        end;
	end;

end;

begin
assign	(f, 'strmatch.in');
reset	(f);
readln 	(f, n);
readln  (f, m);
close	(f);

ln := cBin (n, 1, 2000000);
lm := cBin (m, 1, 2000000);

prefix (n, pn, ln);
KMP;

assign	(f, 'strmatch.out');
rewrite	(f);
writeln (f, nr);
for i := 1 to min(nr, 1000) do
    write (f, pos[i], ' ');
close	(f);
end.