Cod sursa(job #852403)

Utilizator atatomirTatomir Alex atatomir Data 11 ianuarie 2013 10:57:26
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.78 kb
program potrivire;
const  mod1 = 100007;
       mod2 = 100021;
       baza = 73    ;
 
var a,b:ansistring;
    la,lb:longint;
    rez:array[1..2000000]of longint;
    bufin,bufout:array[1..100000]of byte;
    i,l:longint;
    p1,p2:longint;
    hashA1,hashB1,hashA2,hashB2:longint;
    potriv:smallint;
 
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) * baza + ord(b[i+la-1])) mod mod1;
      hashB2 := ((hashB2 - ((ord(b[i-1]) * p2) mod mod2) + mod2) * baza + ord(b[i+la-1])) mod mod2;
 
      if (hashA1 = hashB1) and (hashA2=hashB2) then
      begin
        inc(potriv);
        rez[potriv] := i ;
      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.