Cod sursa(job #175706)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 10 aprilie 2008 12:23:56
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.85 kb
var a,b:array[1..2000001] of char;
    nr,n,m,k,q:longint; c:char;
    v,vv:array[1..2000001] 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(input,'strmatch.in'); reset(input);
m:=0;while not seekeoln do begin inc(m);read(b[m]) end;
readln;
n:=0;while not seekeoln do begin inc(n);read(a[n]) end;
close(input);

prefix;

k:=0; nr:=0;
q:=1;
while(q<=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);vv[nr]:=q-m; {k:=v[k];} end;
    q:=q+1;
  end;


assign(output,'strmatch.out'); rewrite(output);
writeln(nr);
for q:=1 to nr do write(vv[q],' ');
close(output);
end.