Cod sursa(job #174286)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 8 aprilie 2008 18:24:57
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
program strmatch;
var a,b:array[1..2000000] of char;
    f,g:text; nr,n,m,k,q:longint; c:char;
    v:array[1..2000000] of longint;
    vv:array[1..1000] of longint;

procedure prefix;
   begin
     v[1]:=0; k:=0;
     for q:=2 to m do
        begin
          while (k>0)and(b[k+1]<>b[q]) do k:=v[k];
          if b[k+1]=b[q] then k:=k+1;
          v[q]:=k;
        end;
   end;

begin
assign(f,'strmatch.in'); reset(f);
m:=0;while not eoln(f) do begin read(f,c);inc(m);b[m]:=c; end;
readln(f);
n:=0;while not eoln(f) do begin read(f,c);inc(n);a[n]:=c; end;
close(f);

prefix;

k:=0; nr:=0;
q:=1;
while(q<=n)and(nr<1000) do
  begin
    while (k>0)and(b[k+1]<>a[q]) do k:=v[k];
    if b[k+1]=a[q] then k:=k+1;
    if k=m then  begin inc(nr); if nr<1000 then vv[nr]:=q-m; k:=v[k]; end;
    q:=q+1;
  end;


assign(g,'strmatch.out'); rewrite(g);
if nr<1000 then
   begin
     writeln(g,nr);
     for q:=1 to nr do write(g,vv[q],' ');
   end
      else
         begin
           writeln(g,'1000');
           for q:=1 to 1000 do write(g,vv[q],' ');
         end;
close(g);
end.