Cod sursa(job #846223)

Utilizator OpportunityVlad Negura Opportunity Data 1 ianuarie 2013 18:41:33
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.32 kb
const mod1=100007; mod2=100021; p=73;
var fi,fo:text;
    a,b:array[1..3000000]of char;
    s:array[0..10000]of longint;
    p1,p2,i,n,m,h1,h2,ha1,ha2:longint;

procedure writeData;
var i:longint;
 begin
  writeln(fo,s[0]);
  for i:=1 to s[0] do write(fo,s[i],' ');
 end;

procedure solve;
var i:longint;
 begin
  for i:=n+1 to m do
   begin
    h1:=((h1-(ord(b[i-n])*p1) mod mod1+mod1)*p+ord(b[i]))mod mod1;
    h2:=((h2-(ord(b[i-n])*p2) mod mod2+mod2)*p+ord(b[i]))mod mod2;
    if (h1=ha1)and(h2=ha2) then begin inc(s[0]); s[s[0]]:=i-n end;
    if s[0]=1000 then begin writeData; close(fo); close(fi); halt end;
   end;
 end;

procedure readData;
 begin
  while not eoln(fi) do begin inc(n); read(fi,a[n]); end; readln(fi);
  while not eoln(fi) do begin inc(m); read(fi,b[m]); end;
  if n>m then begin write(fo,0); close(fi); close(fo); halt end;
  p1:=1; p2:=1;
  for i:=1 to n do
   begin
    ha1:=(ha1*p+ord(a[i]))mod mod1;
    ha2:=(ha2*p+ord(a[i]))mod mod2;
    if i>1 then begin p1:=(p1*p)mod mod1; p2:=(p2*p)mod mod2; end;
    h1:=(h1*p+ord(b[i]))mod mod1;
    h2:=(h2*p+ord(b[i]))mod mod2;
   end;
  if (h1=ha1)and(h2=ha2) then inc(s[0]);
 end;

BEGIN
 assign(fi,'strmatch.in'); reset(fi); assign(fo,'strmatch.out'); rewrite(fo);

  readData;
  solve;
  writeData;

 close(fi); close(fo);
END.