Pagini recente » Cod sursa (job #664973) | Cod sursa (job #1963291) | Cod sursa (job #2818908) | Cod sursa (job #49501) | Cod sursa (job #186024)
Cod sursa(job #186024)
var s,p:array[1..2000000] of char;
n,m:longint;
procedure citire;
var fin:text;
i:longint;
begin
assign(fin,'strmatch.in'); reset(fin);
i:=1;
while not(eoln(fin)) do begin read(fin,p[i]); inc(i); end;
readln(fin); m:=i-1; i:=1;
while not(eoln(fin)) do begin read(fin,s[i]); inc(i); end;
close(fin);
n:=i-1;
end;
procedure rk(d,q:longint);
var x,hs,hp:longint;
i,j:longint;
ok:boolean;
a:array[1..1001] of longint;
nr:integer;
fout:text;
begin
assign(fout,'strmatch.out'); rewrite(fout);
nr:=0; x:=1;
for i:=1 to m-1 do x:=(d*x) mod q;
hp:=0;
for i:=1 to m do hp:=(d*hp+ord(p[i])) mod q;
hs:=0;
for i:=1 to m do hs:=(d*hs+ord(s[i])) mod q;
i:=1;
while (i<=n-m+1) and (nr<1001) do
begin
if hp=hs then
begin
ok:=true;
for j:=1 to m do
if (p[j]<>s[j+i-1]) then ok:=false;
if ok then begin inc(nr); a[nr]:=i; end;
end;
hs:=(hs+d*q-ord(s[i])*x) mod q;
hs:=(d*hs+ord(s[i+m])) mod q;
inc(i);
end;
writeln(fout,nr);
for i:=1 to nr do write(fout,a[i]-1,' ');
close(fout);
end;
begin
citire;
rk(256,1048576);
end.