Cod sursa(job #177774)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 13 aprilie 2008 16:34:02
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
program kmp;
var A,B : array [1..2000000] of char;
    f,g : text;
    sol : array [1..1000] of longint;
    p : array [1..2000000] of longint;
    i,j,n,m,nr : longint;

procedure prefix;
var k : longint;
begin
k := 0;
p[1] := 0;
for i := 2 to n do begin
while (k>0) and (A[k+1]<>A[i]) do
k := p[k];
if A[k+1]=A[i] then k := k+1;
p[i] := k;
end;
end;


procedure kmp;
var q : longint;
begin
q := 0;
nr := 0;
for i := 1 to m do begin
while (q>0) and (B[i]<>A[q+1]) do
q := p[q];
if B[i]=A[q+1] then q := q+1;
if q=n then begin
            nr := nr+1;
            if nr<=1000 then sol[nr] := i-n;
            q := p[q];
            end;
end;
end;

begin
assign(f,'strmatch.in');
reset(f);
assign(g,'strmatch.out');
rewrite(g);

n := 0;
while not seekeoln(f) do begin
n := n+1;
read(f,A[n]);
end;
readln(f);

if n<2000000 then
begin
m := 0;
while not seekeoln(f) do begin
m := m+1;
read(f,B[m]);
end;
end
else m := n;


if m<>n then begin
prefix;
kmp;
end;


if m<>n then begin
writeln(g,nr);
if nr>1000 then nr := 1000;

for i := 1 to nr do
write(g,sol[i],' ');
end
else begin
        writeln(g,1);
        write(g,0);
        end;

close(f);
close(g);

end.