Cod sursa(job #842432)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 26 decembrie 2012 20:49:51
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.91 kb
program knutt_morris_pratt;
  var f1,f2:text;
      s1,s2:ansistring;
      prefix,sol:array [0..4000000] of longint;
      i,j,l1,l2,k:longint;
      bufin,bufout:array [1..1000000] of char;
begin
  assign(f1,'strmatch.in');
  reset(f1);
  assign(f2,'strmatch.out');
  rewrite(f2);
  settextbuf(f1,bufin);
  settextbuf(f2,bufout);
  readln(f1,s1);
  readln(f1,s2);l1:=length(s1);
  l1:=length(s1);
  l2:=l1+length(s2)+1;
  s2:=s1+'*'+s2;
  for i:=2 to l2 do
    begin
      j:=prefix[i-1];
      while (j>0) and (s2[i]<>s2[j+1]) do
           j:=prefix[j];
      if s2[i]=s2[j+1] then inc(j);
      prefix[i]:=j;
      if j=l1 then begin
                     inc(k);
                     sol[k]:=i-2*l1-1;
                   end;
    end;
  writeln(f2,k);
  if k<1000 then for i:=1 to k do write(f2,sol[i],' ')
            else for i:=1 to 1000 do write(f2,sol[i],' ');
  close(f1);close(f2);
end.