Cod sursa(job #1499772)

Utilizator ili226Vlad Ilie ili226 Data 11 octombrie 2015 08:57:08
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.43 kb
{$R-}
const mod1=100007;
      mod2=100021{666013 21};
      p=73;
var f:text;
    subs:array[1..1000]of longint;
    s1,s2:array[1..2000000]of char;
    p1,p2,ha1,ha2,h1,h2:longint;
    k,i,n,m,j:longint;
begin
assign(f,'strmatch.in');
reset(f);n:=0;
while not(eoln(f)) do
 begin inc(n);
       read(f,s1[n])
 end;
m:=0;readln(f);
while not(eoln(f))do
 begin
  inc(m);
  read(f,s2[m]);
 end;
close(f);
p1:=1;p2:=1;
ha1:=0;ha2:=0;
for i:=1 to n do
 begin
  ha1:=(ha1*p+ord(s1[i]))mod mod1;
  ha2:=(ha2*p+ord(s1[i]))mod mod2;
  if i<>1 then
  begin
  p1:=(p1*p)mod mod1;
  p2:=(p2*p)mod mod2;
  end;
 end;
h1:=0;h2:=0;
for i:=1 to n do
 begin
  h1:=(h1*p+ord(s2[i]))mod mod1;
  h2:=(h2*p+ord(s2[i]))mod mod2;
 end;
k:=0;
if (h1=ha1)and(h2=ha2)then
 begin
  inc(k);
  subs[k]:=1;
 end;
for i:=n+1 to m do
 begin
 h1:=(((h1-(ord(s2[i-n])*p1)mod mod1)+mod1)*p+ord(s2[i]))mod mod1;
 h2:=(((h2-(ord(s2[i-n])*p1)mod mod2)+mod2)*p+ord(s2[i]))mod mod2;
  if (h1=ha1)and(h2=ha2)then
  begin
   inc(k);
   subs[k]:=i-n;
   if k=1000then
    begin
     assign(f,'strmatch.out');
     rewrite(f);
     writeln(f,k);
     for j:=1 to k do
      write(f,subs[j],' ');
     close(f);
     halt;
    end;
  end;
 end;
assign(f,'strmatch.out');
rewrite(f);
writeln(f,k);
if k<=1000 then
for i:=1 to k do
 write(f,subs[i],' ')
           else
for i:=1 to 1000 do
 write(f,subs[i],' ');
close(f);
end.