Cod sursa(job #243321)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 12 ianuarie 2009 17:57:38
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.94 kb
var p,t:array[1..2000001] of char;
    c:char;
    n,m,l,i,q,k:longint;
    v,vv:array[1..2000001] of longint;
procedure prefix;
    begin
      k:=0; v[1]:=0;
      for q:=2 to m do
        begin
          while (k>0)and(p[k+1]<>p[q]) do k:=v[k];
          if p[k+1]=p[q] then inc(k);
          v[q]:=k;
        end;
    end;
begin
assign(input,'strmatch.in'); reset(input);
m:=0;
while not seekeoln do
    begin
      inc(m); read(p[m]);
    end;
n:=0;
readln;
while not seekeoln do
     begin
       inc(n);read(t[n]);
     end;
close(input);
prefix;
q:=0;       l:=0;
for i:=1 to n do
   begin
     while (q>0)and(p[q+1]<>t[i]) do q:=v[q];
     if p[q+1]=t[i] then inc(q);
     if q=m then
        begin
          if l<1000 then begin inc(l); vv[l]:=i-m;end;
          q:=v[q];
        end;
   end;
assign(output,'strmatch.out'); rewrite(output);
writeln(l);
for i:=1 to l do write(vv[i],' ');
close(output);
end.