Cod sursa(job #192992)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 1 iunie 2008 20:39:50
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.34 kb
var a,b:ansistring;
    v:array[1..1000]of longint;
    n,nr,i,j,k:longint;
    p1,p2,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;
   p1:=1;
   p2:=1;
   for i:=1 to k-1 do
     begin
       p1:=(p1*z)mod 100021;
       p2:=(p2*z)mod 100007;
       h1:=(h1*z+ord(a[i]))mod 100021;
       o1:=(o1*z+ord(b[i]))mod 100021;
       h2:=(h2*z+ord(a[i]))mod 100007;
       o2:=(o2*z+ord(b[i]))mod 100007;
     end;
   h1:=(h1*z+ord(a[k]))mod 100021;
   h2:=(h2*z+ord(a[k]))mod 100007;
   for i:=k to n do
     begin
       if i>k then begin o1:=((((o1-ord(b[i-k])*p1+100021) mod 100021+100021)mod 100021)*z+ord(b[i]))mod 100021;
                         o2:=((((o2-ord(b[i-k])*p2+100007) mod 100007+100007)mod 100007)*z+ord(b[i]))mod 100007;
                   end
              else begin o1:=(o1*z+ord(b[i]))mod 100021;
                         o2:=(o2*z+ord(b[i]))mod 100007;
                   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.