Cod sursa(job #209831)

Utilizator FllorynMitu Florin Danut Flloryn Data 25 septembrie 2008 00:07:59
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
    var v,o:array[1..2001000]of char;
        pi,po:array[1..2000100]of longint;
        m,n,i,j,k,p,l,pu,q:longint;
        b,u:int64;
        c:char;
        f:text;
    begin
       assign(f,'strmatch.in');
       reset(f);
      readln(f,v);
      m:=1;
      while(ord(v[m])<>0)do m:=m+1;
      readln(f,o);
      n:=1;
      while(ord(o[n])<>0)do n:=n+1;
      n:=n-1;    m:=m-1;
      pi[1]:=0;  k:=0;
      for i:=2 to m do
                 begin
                      while(k>0)and(v[k+1]<>v[i])do k:=pi[k];
                      if v[k+1]=v[i] then k:=k+1;
                      pi[i]:=k;
                 end;
      q:=0;
      k:=0;
      for i:=1 to n do
                    begin
                        while(q>0)and(v[q+1]<>o[i])do q:=pi[q];
                        if v[q+1]=o[i] then q:=q+1;
                        if q=m then begin k:=k+1;
                        po[k]:=i-m;
                    end;
      end;
      assign(f,'strmatch.out');
      rewrite(f);
      writeln(f,k);
      if k>1000 then k:=1000;
      for i:=1 to k do
      write(f,po[i],' ');
      writeln(f);
      close(f);
   end.