Cod sursa(job #842383)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 26 decembrie 2012 19:30:12
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.96 kb
program knutt_morris_pratt;
  var f1,f2:text;
      s1,s2:ansistring;
      str:array [0..4000000] of char;
      prefix,sol:array [0..4000000] of longint;
      i,j,l1,l2,k:longint;
      bufin,bufout:array [1..100000] 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);
  l2:=l1+length(s2)+1;
  s2:=s1+'*'+s2;
  for i:=1 to l2 do str[i-1]:=s2[i];
  for i:=1 to l2 do
    begin
      j:=prefix[i-1];
      while (j>0) and (str[i]<>str[j]) do
           j:=prefix[j-1];
      if str[i]=str[j] then inc(j);
      prefix[i]:=j;
      if j=l1 then begin
                     inc(k);
                     sol[k]:=i-2*l1;
                   end;
    end;
  writeln(f2,k);
  i:=1;
  while (i<=k) and (i<=1000) do
    begin
      write(f2,sol[i],' ');
      inc(i);
    end;
  close(f1);close(f2);
end.