Cod sursa(job #1367021)

Utilizator casianos1996Marc Casian Nicolae casianos1996 Data 1 martie 2015 15:55:00
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.11 kb
program KMP;
var     x,y:array[1..2000000] of char;
        nr,i,j,k,n,m:longint;
        z,pi,d:array[1..2000000] of longint;
        bufin,bufout:array[1..4000000] of char;
        c:char;

begin
  assign(input,'kmp.in'); reset(input);
  assign(output,'kmp.out'); rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);
  n:=0;
  while not seekeoln(input) do
    begin
      inc(n);
      read(c);
      x[n]:=c;
    end;
  m:=0; readln;
  while not seekeoln(input) do
    begin
      inc(m);
      read(c);
      y[m]:=c;
    end;
  pi[1]:=0; k:=0;
  for i:=2 to n do
    begin
      while (k>0) and (x[i]<>x[k+1]) do
        k:=pi[k];
      if x[i]=x[k+1] then inc(k);
      pi[i]:=k;
    end;
  k:=0; nr:=0;
  for i:=1 to m do
    begin
      while (k>0) and (y[i]<>x[k+1]) do
        k:=pi[k];
      if y[i]=x[k+1] then inc(k);
      if k=n then
        begin
          inc(nr);
          if nr<=1000 then d[nr]:=i-n;
        end;
    end;
  writeln(nr);
  if nr>1000 then nr:=1000;
  for i:=1 to nr do
    write(d[i],' ');
  close(input); close(output);
end.