Cod sursa(job #1365783)

Utilizator casianos1996Marc Casian Nicolae casianos1996 Data 28 februarie 2015 15:31:04
Problema Potrivirea sirurilor Scor 4
Compilator fpc Status done
Runda Arhiva educationala Marime 0.96 kb
program kmp;
var     x,y:ansistring;
        bufin,bufout:array[1..4000002] of byte;
        d,pi:array[1..255] of integer;
        nr,i,k,n,m:longint;
begin
  assign(input,'strmatch.in'); reset(input);
  assign(output,'strmatch.out'); rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);
  readln(x);
  readln(y);
  n:=length(x);
  m:=length(y);
  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;
  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;
      if d[i]=n then inc(nr);
    end;
  writeln(nr); nr:=0;
  for i:=1 to m do
    if d[i]=n then
      begin
        if nr<=1000 then write(i-n,' ')
        else break;
        inc(nr);
      end;
  close(input); close(output);
end.