Cod sursa(job #186020)

Utilizator EcthorIorga Dan Ecthor Data 26 aprilie 2008 16:11:32
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
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) 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.