Cod sursa(job #192984)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 1 iunie 2008 20:10:21
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.32 kb
var a,b:ansistring;
    v:array[1..1000]of longint;
    n,nr,i,j,k:longint;
    p,h1,z,l,o1,aux,h2,o2:longint;
    f:text;
begin
   assign(f,'strmatch.in');
   reset(f);
   readln(f,a);
   readln(f,b);
   close(f);
   k:=length(a);
   n:=length(b);
   z:=67;
   p:=z;
   for i:=1 to k-1 do
     begin
       p:=(p*z)mod 1000021;
       h1:=(h1*z+ord(a[i]))mod 1000021;
       o1:=(o1*z+ord(b[i]))mod 1000021;
       h2:=(h2*z+ord(a[i]))mod 1000007;
       o2:=(o2*z+ord(b[i]))mod 1000007;
     end;
   h1:=(h1*z+ord(a[k]))mod 1000021;
   h2:=(h2*z+ord(a[k]))mod 1000007;
   for i:=k to n do
     begin
       o1:=(o1*z+ord(b[i]))mod 1000021;
       o2:=(o2*z+ord(b[i]))mod 1000007;
       if(i>k)then begin aux:=((ord(b[i-k]))*p)mod 1000021;
                         o1:=o1-aux;
                         aux:=((ord(b[i-k]))*p)mod 1000007;
                         o2:=o2-aux;
                         if o1<0 then o1:=o1+1000021;
                         if o2<0 then o2:=o2+1000007;
                   end;
       if(o1=h1)and(o2=h2)then begin nr:=nr+1;
                                     if(nr<=1000)then v[nr]:=i-k;
                               end;
     end;
   assign(f,'strmatch.out');
   rewrite(f);
   writeln(f,nr);
   for i:=1 to nr do
   write(f,v[i],' ');
   writeln(f);
   close(f);
end.