Cod sursa(job #1179726)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 29 aprilie 2014 09:15:24
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
program rabinkrap;
const mod1=100007;
      mod2=100021;
      p=101;

  var s,s1:ansistring;
    n,m,i,j,ha,hb,ha1,hb1,nr,p1,p2:longint;
    sol,a,b:array[1..2000000] of longint;
  begin
    assign(input,'grader_test21.in');
    assign(output,'strmatch.out');
    reset(input);
    rewrite(output);
    readln(s);
    readln(s1);
    m:=length(s);
    n:=length(s1);

    for i:=1 to m do a[i]:=ord(s[i]);
    for i:=1 to n do b[i]:=ord(s1[i]);


    p1:=1; p2:=1;
    for i:=1 to m do
      begin
        ha:=(ha*p+a[i]) mod mod1;
        ha1:=(ha1*p+a[i]) mod mod2;
        hb:=(hb*p+b[i]) mod mod1;
        hb1:=(hb1*p+b[i]) mod mod2;

        if i<>1 then begin
            p1:=(p1*p) mod mod1;
            p2:=(p2*p) mod mod2;
            end;
      end;
    for i:=m+1 to n do
      begin
        if (ha=hb)and(ha1=hb1)
         then begin
           inc(nr);
           sol[nr]:=i-m;
           end;
         hb:=((hb-(p1*b[i-m])mod mod1+mod1)*p+b[i]) mod mod1;
         hb1:=((hb1-(p2*b[i-m])mod mod2+mod2)*p+b[i]) mod mod2;
      end;
  writeln(nr);
  for i:=1 to nr do write(sol[i]-1,' ');
  close(output);
end.