Cod sursa(job #567540)

Utilizator andrei31Andrei Datcu andrei31 Data 30 martie 2011 10:10:43
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
var t:array[1..2000000] of char;
    p:array[1..2000000] of char;
    urm:array[1..2000000] of longword;
    ras:array[1..1000] of longword;
    n,m,nr:longword;
    buf:array[1..100000] of char;
procedure citire;
begin
assign(input,'strmatch.in');settextbuf(input,buf);reset(input);
while not seekeoln(input) do
 begin
 inc(m);read(p[m]);
 end;
readln;
while not seekeoln(input) do
 begin
 inc(n);read(t[n]);
 end;
close(input);
end;

procedure urmatorul;
var q,k:longword;
begin
k:=0;
urm[1]:=0;
for q:=2 to m do
 begin
 while (k>0) and (p[k+1]<>p[q]) do k:=urm[k];
 if p[k+1]=p[q] then inc(k);
 urm[q]:=k;
 end;
end;

procedure kmp;
var i,q:longword;
begin
q:=0;
urmatorul;
for i:=1 to n do
 begin
 while (q>0) and (p[q+1]<>t[i]) do q:=urm[q];
 if (p[q+1]=t[i]) then inc(q);
 if q=m then
           begin
            inc(nr);
            q:=urm[q];
            if nr<=1000 then ras[nr]:=i-m;
           end;
 end;
end;

procedure afiseaza;
var i,go:word;
begin
assign(output,'strmatch.out');settextbuf(output,buf);rewrite(output);
if nr>1000 then go:=1000 else go:=nr;
writeln(nr);
for i:=1 to go do
write(ras[i],' ');
close(output);
end;

begin
citire;
kmp;
afiseaza;
end.