Cod sursa(job #170937)

Utilizator kolapsysPostelnicu Dan Marian kolapsys Data 3 aprilie 2008 15:50:16
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.38 kb
{ http://infoarena.ro/problema/strmatch }
{$LONGSTRINGS ON}
type vector=array[1..2000000] of longint;
var a,b:string;
    nr,nb,na:longint;
    lim,i:word;
    v,pi:vector;
    f,g:text;
{ Algoritmul === Knuth-Morris-Pratt === }
procedure prefix;
var i,k:longint;
begin
      k:=0;
      pi[1]:=0;
      for i:=2 to na do
         begin
         while  (k>0) and (a[i]<>a[k+1]) do
                k:=pi[k];
         if a[k+1]=a[i] then k:=k+1;
         pi[i]:=k;
         end;
end;

procedure kmp;
var i,k:longint;
begin
   k:=0;
   for i:=1 to nb do
        begin
        while (k>0) and (a[k+1]<>b[i]) do
                k:=pi[k];
        if a[k+1]=b[i] then inc(k);
        if k=na then begin
                    inc(nr);
                    if nr<=1000 then v[nr]:=i-na;
                    k:=pi[k];
                    end;
        end;
end;
{ ===== Sfasit cautare ===== }

begin
   assign(f,'strmatch.in'); reset(f);
   assign(g,'strmatch.out'); rewrite(g);
   readln(f,a);
   read(f,b);
   na:=length(a);
   nb:=length(b);
   if na>nb then writeln(g,0)
            else begin
                 prefix;
                 kmp;
                 writeln(g,nr);
                 if nr>1000 then lim:=1000
                           else lim:=nr;
                 for i:=1 to lim do write(g,v[i],' ');
                 end;
   close(f); close(g);
end.