Pagini recente » Cod sursa (job #1768881) | Cod sursa (job #1912894) | Cod sursa (job #554712) | Cod sursa (job #1763299) | Cod sursa (job #1171425)
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: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
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[0]:=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) and (u<1000) 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.