Cod sursa(job #1173805)

Utilizator vasica38Vasile Catana vasica38 Data 20 aprilie 2014 21:32:16
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.91 kb
program p3121;
const m1=100007;
const m2=1000021;
const p=97;
var a,b:array[0..2000000] of char;
    b1,b2:array[0..1 shl 21] of char;
    i,n,j,k,u,p2,p1,m,u1:longint;
    hash1,hash2,hash3,hash4:longint;
    match:array[0..1005] of longint;
    f,g:text;




{function t(c:char):longint;
begin
t:=ord(c);
end;
  }


begin
assign(f,'strmatch.in');reset(F);
assign(g,'strmatch.out');rewrite(G);
settextbuf(f,b1);
settextbuf(g,b2);
while not eoln(f)  do begin
                inc(N);
                read(F,a[n]);
                        end;
readln(F);
while not eoln(f) do begin
                inc(M);
                read(f,b[m]);
                        end;
if n >m then
                writeln(g,'0')
                else begin


p1:=1;
p2:=1;
 for i:=1 to n do begin
        hash1:=(hash1*p+ord(a[i])) mod m1;
        hash2:=(hash2*p+ord(a[i])) mod m2;
        hash3:=(hash3*p + ord(b[i])) mod m1;
        hash4:=(hash4*p + ord(b[i])) mod m2;
        if i>1 then begin
        p1:=(p1*p) mod m1;
        p2:=(p2*p) mod m2;
                end;
                end;
if ( hash1=hash3)  and (hash2=hash4) then begin
                inc(U);
                inc(u1);
                match[0]:=1;
                                end;
for i:=n+1 to m do begin
        hash3:=((hash3-((ord(b[i-n])*p1) mod m1) + m1) * p +ord(b[i])) mod m1;
        hash4:=((hash4-((ord(b[i-n])*p2) mod m2) + m2) * p +ord(b[i])) mod m2;
        if (hash1=hash3) and (hash2=hash4)  then begin
                if u<1000 then begin

                        inc(U);inc(u1);
                        match[u]:=i-n;
                              end
                              else inc(u1);
                                end;
                                end;
writeln(g,u1);
if u1>1000 then u1:=1000;
for i:=1 to   u do
        write(G,match[i],' ');
              end;
close(F);
close(G);
end.