Pagini recente » Cod sursa (job #881198) | Cod sursa (job #284894) | Cod sursa (job #1243305) | Cod sursa (job #920520) | Cod sursa (job #1171388)
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.