Cod sursa(job #1171388)

Utilizator vasica38Vasile Catana vasica38 Data 15 aprilie 2014 17:26:10
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 2.66 kb
program p3121;
const m1=20233;
const m2=20323;
const p=73;
var a,b:ansistring;
    i,n,j,k,u,p2,p1: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);
readln(f,a);
readln(f,b);

{p1:=1;
p2:=1;
for i:=1 to length(A) do begin
        hash1:=(hash1*p + ord(a[i])-48 ) mod m1;
        hash2:=(hash2*p + ord(a[i])-48) mod m2;
        p1:=(p1*p) mod m1;
        p2:=(p2*p) mod m2;
                end;
for i:=1 to length(A) do begin
        hash3:=(hash3*p+ ord(b[i])-48) mod m1;
        hash4:=(hash4*p+ord(b[i])-48) mod m2;
                        end;
if (hash1=hash3) and(hash2=hash4) then begin
                 match[1]:=1;
                 inc(u);
                        end;
for i:=length(A) to length(B) do begin
                hash3:=((hash3-((ord(b[i-length(A)])-48)*p1) mod m1 + m1 )*p +ord(b[i])-48) mod m1;
                hash4:=((hash4-((ord(b[i-length(A)])-48)*p2) mod m2 + m2 )*p +ord(b[i])-48) mod m2;
                if (hash3=hash1) and (hash2=hash4) then begin
                                match[i-length(A)+1]:=1;
                                inc(U);
                                                end;
                                end;
i:=1;
writeln(g,u);
u:=0;
while (i<=length(B)) and (u<=1000) do
        begin
        if match[i]=1 then begin
                write(g,i,' ');
                inc(U);
                        end;
        inc(I);
                end; }

p1:=1;
p2:=1;
 for i:=1 to length(A) 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;
for i:=1 to length(b) do begin

                end;
if ( hash1=hash3)  and (hash2=hash4) then begin
                inc(U);
                match[1]:=1;
                                end;
for i:=length(a)+1 to length(b) do begin
        hash3:=((hash3-((t(b[i-length(a)])*p1) mod m1) + m1) * p +t(b[i])) mod m1;
        hash4:=((hash4-((t(b[i-length(a)])*p2) mod m2) + m2) * p +t(b[i])) mod m2;
        if (hash1=hash3) and (hash2=hash4) then begin
                        match[i-length(A)+1]:=1;
                        inc(u);
                                end;
                                end;
writeln(g,u);
for i:=1 to   length(b) do
        if match[i]=1 then write(g,i-1,' ');

close(F);
close(G);
end.