Pagini recente » Cod sursa (job #2101055) | Cod sursa (job #1390142) | Cod sursa (job #139062) | Cod sursa (job #865062) | Cod sursa (job #186018)
Cod sursa(job #186018)
var s,p:array[1..2000000] of char;
n,m:integer;
procedure citire;
var fin:text;
i:integer;
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:integer;
ok:boolean;
a:array[1..1001] of integer;
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) 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,32768);
end.