Cod sursa(job #1171400)

Utilizator vasica38Vasile Catana vasica38 Data 15 aprilie 2014 17:48:56
Problema Potrivirea sirurilor Scor 38
Compilator fpc Status done
Runda Arhiva educationala Marime 1.75 kb
program p3121;
const m1=20233;
const m2=20323;
const p=73;
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:longint;
    hash1,hash2,hash3,hash4:longint;
    match:array[0..2000000] 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


readln(f,b);
p1:=1;
p2:=1;
 for i:=1 to n do begin
        hash1:=(hash1*p+t(a[i])) mod m1;
        hash2:=(hash2*p+t(a[i])) mod m2;
        hash3:=(hash3*p + t(b[i])) mod m1;
        hash4:=(hash4*p + t(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);
                match[1]:=1;
                                end;
for i:=n+1 to m do begin
        hash3:=((hash3-((t(b[i-n])*p1) mod m1) + m1) * p +t(b[i])) mod m1;
        hash4:=((hash4-((t(b[i-n])*p2) mod m2) + m2) * p +t(b[i])) mod m2;
        if (hash1=hash3) and (hash2=hash4) then begin
                        inc(U);
                        match[u]:=i-n;
                                end;
                                end;
writeln(g,u);
if u>1000 then u:=1000;
for i:=1 to   u do
        write(G,match[i],' ');
              end;
close(F);
close(G);
end.