Cod sursa(job #170681)

Utilizator kolapsysPostelnicu Dan Marian kolapsys Data 3 aprilie 2008 00:52:51
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.27 kb
{ http://infoarena.ro/problema/strmatch }
type vector=array[1..1000000] of longint;
var a,b:string;
    n,k:longint;
    lim,i:word;
    v:vector;
    f,g:text;
{ Algoritmul === Knuth-Morris-Pratt === }
procedure cauta(a,b:string;var v:vector;var k:longint);
var
   pi:array[1..1000]of longint;
   i,j,m,n,rez:longint;

   procedure prefix;
   var k,i:longint;
   begin
      m:=length(a);
      k:=0; pi[1]:=0;
      for i:=2 to m do
         begin
         while  (k>0) and (a[i]<>a[k]) do
                k:=pi[k];
         if a[k+1]=a[i] then k:=k+1;
         pi[i]:=k;
         end;
   end;

begin
   m:=length(a); n:=length(b);
   j:=0; k:=0;
   prefix;
   for i:=1 to n do
        begin
        while (j>0) and (a[j+1]<>b[i]) do
                j:=pi[j];
        if a[j+1]=b[i] then j:=j+1;
        if j=m then begin
                    inc(k);
                    if k<1000 then v[k]:=i-m+1;
                    end;
        end;
end;
{ ===== Sfasit cautare ===== }

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