Cod sursa(job #568489)

Utilizator promix2012petruta andrei promix2012 Data 31 martie 2011 12:07:50
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.97 kb
var s,t:ansistring;
    f,g:text;
    urm,v:array[0..2000000] of longint;
    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);
   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];
            end;
      end;
   writeln(g,nr);
   for i:=1 to nr do
      write(g,v[i],' ');
   close(f);
   close(g);
end.