Cod sursa(job #709858)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 8 martie 2012 17:28:36
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.36 kb
Program strmatch_arena_edu;
var fi,fo : text; i,m,n,k,nrsol : longint;
    a,b : array[0..2000000] of char;
    sol:array[0..1010] of longint; pi:array[0..2000000] of longint;
begin
   assign(fi,'strmatch.in'); reset(fi);
   assign(fo,'strmatch.out'); rewrite(fo);
   m:=0; n:=0; pi[1]:=0; k:=0;
   while not(seekeoln(fi)) do begin
                              m:=m+1;
                              read(fi,a[m]);
                              end;
   readln(fi);
   while not(seekeoln(fi)) do begin
                              n:=n+1;
                              read(fi,b[n]);
                              end;

   for i:=2 to m do begin
                    while (k>0) and (a[k+1]<>a[i]) do k:=pi[k];
                    if a[k+1]=a[i] then k:=k+1;
                    pi[i]:=k;
                    end;

   k:=0;
   for i:=1 to n do begin
                    while (k>0) and (a[k+1]<>b[i]) do k:=pi[k];
                    if a[k+1]=b[i] then k:=k+1;
                    if k=m then begin
                                k:=pi[m];
                                nrsol:=nrsol+1;
                                if nrsol<=1000 then sol[nrsol]:=i-m;
                                end;
                    end;

   writeln(fo,nrsol);
   if nrsol>1000 then nrsol:=1000;
   for i:=1 to nrsol do write(fo,sol[i],' ');
   close(fi); close(fo);
end.