Cod sursa(job #846204)

Utilizator OpportunityVlad Negura Opportunity Data 1 ianuarie 2013 18:16:18
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.17 kb
const mdl=100000021;
var fi,fo:text;
    a,b:array[1..3000000]of char;
    s:array[0..10000]of longint;
    i,n,m,h1,h2:longint;
 
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;
 end;
 
function check(k:longint):boolean;
var i:longint;
 begin
  check:=true;
  for i:=k to k+n-1 do
   if b[i]<>a[i-k+1] then
    begin check:=false; exit end;
 end;
 
procedure writeData;
 begin
  writeln(fo,s[0]);
  for i:=1 to s[0] do write(fo,s[i],' ');
 end;
 
procedure solve;
 begin
  if n>m then begin write(fo,'0'); close(fo); halt; end;
  h1:=ord(a[1]);
  for i:=2 to n do h1:=(h1+ord(a[i])) mod mdl;
  h2:=ord(b[1]);
  for i:=2 to n do h2:=(h2+ord(b[i])) mod mdl;
  for i:=n to m do
   begin
    if (h1=h2)and(check(i-n+1)) then begin inc(s[0]); s[s[0]]:=i-n; end;
    if s[0]=1000 then begin writeData; close(fo); halt; end;
    dec(h2,ord(b[i-n+1]));
    h2:=(h2+ord(b[i+1])) mod mdl;
   end;
 end;
 
BEGIN
 assign(fi,'strmatch.in'); reset(fi); assign(fo,'strmatch.out'); rewrite(fo);
 
  readData;
  solve;
  writeData;
 
 close(fi); close(fo);
END.