Cod sursa(job #1367028)

Utilizator casianos1996Marc Casian Nicolae casianos1996 Data 1 martie 2015 15:59:38
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.1 kb
program KMP;
var     x,y:array[1..2000000] of char;
        nr,i,j,k,n,m:longint;
        z,d,pi:array[1..2000000] of longint;
        bufin,bufout:array[1..4000000] of 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(x[n]);
    end;
  m:=0; readln;
  while not seekeoln(input) do
    begin
      inc(m);
      read(y[m]);
    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);
      d[i]:=k;
    end;
  nr:=0;
  for i:=1 to m do
    if d[i]=n then
      begin
        inc(nr);
        if nr<=1000 then z[nr]:=i-N;
      end;
  writeln(nr);
  if nr>1000 then nr:=1000;
  for i:=1 to nr do
    write(z[i],' ');
  close(input); close(output);
end.