Cod sursa(job #852382)

Utilizator atatomirTatomir Alex atatomir Data 11 ianuarie 2013 10:10:48
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.92 kb
program potrivire;
const  mod1 = 100007;
       mod2 = 100021;
       baza = 73    ;

var a,b:ansistring;
    la,lb:longint;
    rez:array[1..1003]of longint;
    bufin,bufout:array[1..65000]of byte;
    i,l:longint;
    p1,p2:longint;
    hashA1,hashB1,hashA2,hashB2:longint;
    potriv:longint;

begin
  assign(input,'strmatch.in'); reset(input);
  assign(output,'strmatch.out'); rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);

  readln(a);    la := length(a);
  readln(b);    lb := length(b);

  p1 := 1; p2 := 1;

  hashA1 := 0; hashA2 := 0;
  for i := 1 to la do
  begin
    hashA1 := ( hashA1 * baza + ord(a[i]) ) mod mod1 ;
    hashA2 := ( hashA2 * baza + ord(a[i]) ) mod mod2 ;
    if i > 1 then
    begin
      p1 := (p1 * baza) mod mod1;
      p2 := (p2 * baza) mod mod2;
    end;
  end;

  potriv :=0;  hashB1 :=0; hashB2 := 0;

  if la <= lb then
  begin
    for i := 1 to la do
    begin
      hashB1 := (  hashB1 * baza + ord(b[i]) ) mod mod1;
      hashB2 := (  hashB2 * baza + ord(b[i]) ) mod mod2;
    end;

    potriv := 0;

    if (hashA1 = hashB1) and (hashA2 = hashB2) then
    begin
      inc(potriv);
      rez[potriv] := 1;
    end;

    l := lb-la+1;

    for i := 2 to l do
    begin
      hashB1 := (hashB1 - ((ord(b[i-1]) * p1) mod mod1) + mod1) mod mod1;
      hashB2 := (hashB2 - ((ord(b[i-1]) * p2) mod mod2) + mod2) mod mod2;

      hashB1 := (((hashB1 * baza)mod mod1) + ord(b[i+la-1])) mod mod1;
      hashB2 := (((hashB2 * baza)mod mod2) + ord(b[i+la-1])) mod mod2;

      if (hashA1 = hashB1) and (hashA2=hashB2) then
      begin
        inc(potriv);
        if potriv <= 1000 then
        begin
          rez[potriv] := i ;
        end;
      end;
    end;

  end;

  writeln(potriv);
  if potriv >= 1000 then potriv := 1000;
  for i := 1 to potriv do
    write(rez[i] - 1,' ');

  close(input);
  close(output);
end.