Cod sursa(job #174842)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 9 aprilie 2008 12:08:46
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.86 kb
var a,b:array[1..2000000] of char;
    nr,n,m,k,q:longint; c:char;
    v,vv:array[1..2000000] 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(f) do begin read(c);inc(m);b[m]:=c; end;
readln;
n:=0;while not seekeoln(f) do begin read(c);inc(n);a[n]:=c; 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.