Cod sursa(job #156231)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 12 martie 2008 13:51:14
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.86 kb
//Knuth Morris Pratt
const nmax=2000000;
var fi,fo:text;
    n,m,i,k,x,ct:longint;
    T,P:ansistring;
    Next,sol:array[0..nmax]of longint;
begin
  assign(fi,'strmatch.in'); reset(fi);
  assign(fo,'strmatch.out'); rewrite(fo);
  readln(fi,P); readln(fi,T);
  n:=length(T); m:=length(P);
  Next[1]:=0; k:=0;
  for i:=2 to m do
    begin
      while (k>1)and(P[k+1]<>P[i]) do
        k:=Next[k];
      if P[k+1]=P[i] then inc(k);
      Next[i]:=k;
    end;
  x:=0; ct:=0;
  for i:=1 to n do
    begin
      while (x>1)and(P[x+1]<>T[i]) do x:=Next[x];
      if P[x+1]=T[i] then inc(x);
      if x=m then
        begin
          inc(ct);
          if ct<=1000 then sol[ct]:=i-m;
          x:=Next[x];
        end;
    end;
  writeln(fo,ct);
  if ct>1000 then ct:=1000;
  for i:=1 to ct do
    write(fo,sol[i],' ');
  close(fi);
  close(fo);
end.