Cod sursa(job #1211914)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 23 iulie 2014 14:52:23
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
program zfunction;
  var a,b:ansistring;
      bufin,bufout:array[1..100000] of byte;
      z,ans:array[1..4000001]of longint;
      n,l,r,i,j,len:longint;


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

  assign(output,'strmatch.out');
  rewrite(output);


  for i:=1 to 4000001 do z[i]:=0;

  readln(a);len:=length(a);
  readln(b);
  a:=a+'#'+b;  l:=1;r:=1; n:=length(a);
  for i:=2 to n do
    begin
      if i>r then
        begin
          z[i]:=0;
          while (n>=i+z[i])and(a[z[i]+1]=a[i+z[i]]) do inc(z[i]);
          if z[i]<>0 then
            begin
              l:=i;
              r:=i+z[i]-1;
            end;
        end else
        begin
          z[i]:=z[i-l];
          if r-i+1<z[i] then z[i]:=r-i+1;
          while (n>=i+z[i])and(a[z[i]+1]=a[i+z[i]]) do inc(z[i]);
          r:=i+z[i]-1;
        end;
    end;
  j:=0;
  for i:=len+2 to n do if z[i]=len then
    begin
      inc(j);
      ans[j]:=i-len-2;
    end;
  writeln(j);
  for i:=1 to j do write(ans[i],' ');
  close(output);
end.