Cod sursa(job #842181)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 26 decembrie 2012 13:35:04
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.9 kb
program knutt_mrgan_pratt;
  var f,f2:text;
      s:array [0..4000000] of char;
      pre:array [0..4000000] of longint;
      length,length2,i,j,k:longint;
      bufin,bufout:array [1..64000] of char;
begin
  assign(f,'strmatch.in');
  reset(f);
  assign(f2,'strmatch.out');
  rewrite(f2);
  settextbuf(f,bufin);
  settextbuf(f2,bufout);
  while not seekeoln(f) do
    begin
      read(f,s[i]);
      inc(i);
    end;
  length:=i;
  s[i]:='&';inc(i);
  readln(f);
  while not seekeof(f) do
    begin
      read(f,s[i]);
      inc(i);
    end;
  length2:=i;
  for i:=1 to length2 do
    begin
      j:=pre[i-1];
      while (j>0) and (s[i]<>s[j]) do j:=pre[j-1];
      if (s[i]=s[j]) then inc(j);
      pre[i]:=j;
      if pre[i]=length then inc(k);
    end;
  writeln(f2,k);
  for i:=length to length2 do if pre[i]=length then write(f2,i-2*length,' ');
  close(f);
  close(f2);
end.