Cod sursa(job #1499765)

Utilizator ili226Vlad Ilie ili226 Data 11 octombrie 2015 08:24:52
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
{$R-}
const mod1=100007;
      mod2={100021}666013;
      p=73;
var f:text;
    subs:array[1..250]of byte;
    s1,s2:string;
    p1,p2,ha1,ha2,h1,h2:longint;
    k,i,n,m:byte;
begin
assign(f,'strmatch.in');
reset(f);
readln(f,s1);
readln(f,s2);
close(f);
n:=length(s1);
m:=length(s2);
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;
  end;
 end;
assign(f,'strmatch.out');
rewrite(f);
writeln(f,k);
for i:=1 to k do
 write(f,subs[i],' ');
close(f);
end.