Pagini recente » Cod sursa (job #2589122) | Cod sursa (job #28034) | Cod sursa (job #2614558) | Cod sursa (job #325167) | Cod sursa (job #298582)
Cod sursa(job #298582)
//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.