Cod sursa(job #168931)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 31 martie 2008 21:25:00
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.06 kb
program strm2;
var A,B : array [1..2000010] of char;
    p : array [1..2000010] of longint;
    sol : array [1..1000] of longint;
    nr,i,n : longint;
procedure pi;
var k,i : longint;
begin
k := 0;
i := 2;
while ((A[i]>='a') and (A[i]<='z')) or ((A[i]>='A') and (A[i]<='Z')) do begin
while (k>0) and (A[i]=A[k+1]) do
k := p[k];
if A[i]=A[k+1] then k := k+1;
p[i] := k;
i := i+1;
end;
n := i-1;
end;

procedure kmp;
var k,i : longint;
begin
k := 0;
i := 1;
nr := 0;
while ((B[i]>='a') and (B[i]<='z')) or ((B[i]>='A') and (B[i]<='Z')) do begin
while (k>0) and (B[i]<>A[k+1]) do
k := p[i];
if B[i]=A[k+1] then k := k+1;
if k=n then begin
            nr := nr+1;
            if nr<= 1000 then sol[nr] := i-n;
            k := p[k];
            end;
i := i+1;
end;
end;

begin
assign(input,'strmatch.in');
reset(input);
assign(output,'strmatch.out');
rewrite(output);

readln(input,A);
read(input,B);

pi;
kmp;

writeln(nr);
if nr>1000 then nr := 1000;
for i := 1 to nr do
write(sol[i],' ');

close(input);
close(output);

end.