Cod sursa(job #174269)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 8 aprilie 2008 18:15:12
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.07 kb
program strmatch;
var a,b:array[1..2000000] of char;
    f,g:text;
    nr,n,m,k,q:longint;
    v:array[1..2000000] of longint;
    c:char;
    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;
for q:=1 to n 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
  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.