Cod sursa(job #186038)

Utilizator EcthorIorga Dan Ecthor Data 26 aprilie 2008 16:54:52
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.13 kb
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:int64);
var x,hs,hp:int64;
    i,j:longint;
    ok:boolean;
    a:array[1..1000] of longint;
    nr:longint;
    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); if nr<1001 then 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); i:=1;
while (i<=nr) and (i<1000) do begin write(fout,a[i]-1,' '); inc(i); end;
close(fout);
end;

begin
citire;
rk(256,1 shl 54);
end.