Cod sursa(job #757047)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 10 iunie 2012 22:05:55
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.1 kb
Program Potrivirea_sirurilor;
 var s1,s2:ansistring;
     sol,urm:array [1..2000005] of longint;
     b1,b2:array [1..1 shl 17] of char;
     n,m,i,q,nr:longint;
     fi,fo:text;
procedure urmatorul;
 var k,q:longint;
begin
 urm[1]:=0; k:=0;
  for q:=2 to m do begin
          while (k>0) and (s1[q]<>s1[k+1]) do k:=urm[k];
           if s1[k+1]=s1[q] then inc(k);
            urm[q]:=k;
             end;
end;
begin
 assign(fi,'strmatch.in');
  assign(fo,'strmatch.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo); readln(fi,s1); read(fi,s2);
  n:=length(s2); m:=length(s1); urmatorul;
   for i:=1 to n do begin
                 while (q>0) and (s2[i]<>s1[q+1]) do q:=urm[q];
                  if s1[q+1]=s2[i] then inc(q);
                   if q=m then begin
                                inc(nr); if nr<=1000 then sol[nr]:=i-m;
                                q:=urm[q];
                                end;
                   end;
                  writeln(fo,nr);
                 if nr<1000 then nr:=1000;
   for i:=1 to nr do write(fo,sol[i],' ');
  close(fo);
end.