Cod sursa(job #1211878)

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

begin
  assign(input,'strmatch.in');
  reset(input);
  settextbuf(input,bufin);
  assign(output,'strmatch.out');
  rewrite(output);
  settextbuf(output,bufout);

  readln(a);len:=length(a);
  readln(b);
  a:=a+'#'+b;  l:=1;r:=1; n:=length(a);
  for i:=2 to length(a) 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 inc(j);
  writeln(j);
  for i:=len+2 to n do if z[i]=len then write(i-len-2, ' ');
  close(output);
end.