Cod sursa(job #293390)

Utilizator EcthorIorga Dan Ecthor Data 1 aprilie 2009 18:58:15
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.85 kb
program gigel;
var n,m:longint;
	t,p:array[0..2000000] of char;
	pre,ap:array[0..2000000] of longint;
	q,i,nr:longint;
	fout:text;

procedure citire;
var fin:text;
begin
assign(fin,'strmatch.in'); reset(fin);
n:=0; m:=0;
while not(eoln(fin)) do begin inc(m); read(fin,p[m]) end;
readln(fin);
while not(eoln(fin)) do begin inc(n); read(fin,t[n]) end;
close(fin);
end;

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

begin
citire;
prefix;
q:=0; nr:=0;
for i:=1 to n do 
	begin
	 while (q>0) and (p[q+1]<>t[i]) do q:=pre[q];
	 if p[q+1]=t[i] then inc(q);
	 if q=m then begin inc(nr); ap[nr]:=i-m; q:=pre[q]; end;
	end;
assign(fout,'strmatch.out'); rewrite(fout); writeln(fout,nr);
for i:=1 to nr do write(fout,ap[i],' ');
close(fout);
end.