Cod sursa(job #360779)

Utilizator ScriamTertiuc Afanasie Scriam Data 1 noiembrie 2009 22:00:19
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 0.92 kb
Program seti;
var r,j,l : integer;
    v : array[1..1500] of integer;
    f,g : text;
    A,B : string;
    urm : array[1..2000000] of integer;


Procedure urmatorul(p : string);
var k,q : integer;

begin
k:=0;
urm[1]:=0;
for q:=2 to length(p) do
begin
while (k>0) and (p[k+1]<>p[q]) do k:=urm[k];
if p[k+1]=p[q] then inc(k);
urm[q]:=k;
end;
end;




Procedure KMP(T,P : string);
var q,i,m : integer;

begin
j:=1;
q:=0;
m:=length(P);
urmatorul(P);
for i:=1 to length(T) do
begin
  while (q>0) and (P[q+1]<>T[i]) do q:=urm[q];
  if P[q+1]=T[i] then inc(q);
  if q=length(p) then
  begin
  inc(r);
  v[j]:=i-m;
  inc(j);
  if j>1000 then j:=1001;
  q:=urm[q];
  end;
end;
end;




begin
assign(f,'strmatch.in');
reset(f);
readln(f,A);
readln(f,B);
KMP(B,A);
close(f);
assign(g,'strmatch.out');
rewrite(g);
writeln(g,r);
for l:=1 to j-1 do write(g,v[l],' ');
close(g);
end.