Cod sursa(job #1212907)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 26 iulie 2014 14:22:44
Problema Potrivirea sirurilor Scor 32
Compilator fpc Status done
Runda Arhiva educationala Marime 0.81 kb
program kmp;
  var bufin,bufout:array[1..100000]of byte;
      a,b:ansistring;
      n,m,i,j:longint;
      pre:array[1..4000001]of longint;


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

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