Cod sursa(job #1365776)

Utilizator mihai1996Toader Mihai mihai1996 Data 28 februarie 2015 15:23:14
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
program kmp;
var i,j,n,m,k,nr:longint;
    x,y:array[1..2000000] of char;
    pi,d,z:array[1..2000000] of longint;
    BUFIN,BUFOUT:array[1..400000] of char;
begin
  assign(input,'strmatch.in'); reset(input);
  assign(output,'strmatch.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;
    {
  for i:=1 to n do
    write(x[i]);
  writeln;
  for j:=1 to m do
     write(y[j]);    }

  k:=0;
  pi[1]:=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;
  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);
        z[nr]:=i-N;
    //    if nr>1000 then
       //   break;
      end;
  writeln(nr);
  for i:=1 to nr do
    write(z[i],' ');
  close(input);
  close(output);
end.