Cod sursa(job #582061)

Utilizator promix2012petruta andrei promix2012 Data 14 aprilie 2011 20:36:17
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.11 kb
var s,t:ansistring;
    f,g:text;
    urm,v:array[0..2000000] of longint;
    bufin,bufout:array[1..65000] of byte;
    n,k,m,i,x,nr:longint;

procedure prefix(m:longint);
var k,x:integer;
begin
   k:=0;
   urm[1]:=0;
   for x:=2 to m do
      begin
         k:=urm[x-1];
         while(k>0)and(s[k+1]<>s[x])do
            k:=urm[k];
         if s[k+1]=s[x] then
            inc(k);
         urm[x]:=k;
      end;
end;

begin
   assign(f,'strmatch.in');reset(f);
   assign(g,'strmatch.out');rewrite(g);
   settextbuf(f,bufin);
   settextbuf(g,bufout);
   readln(f,s);
   readln(f,t);

   m:=length(s);
   n:=length(t);
   prefix(m);
   k:=0;
   nr:=0;
   for x:=1 to n do
      begin
         while(k>0)and(s[k+1]<>t[x])do
            k:=urm[k];
         if s[k+1]=t[x] then
            inc(k);
         if k=m then
            begin
               inc(nr);
               v[nr]:=x-m;
               k:=urm[k];
               if nr=1000 then
               break;
            end;
      end;
   writeln(g,nr);
   for i:=1 to nr do
      write(g,v[i],' ');
   close(f);
   close(g);
end.