Cod sursa(job #293618)

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

procedure citire;
var fin:text;
begin
assign(fin,'strmatch.in'); reset(fin);
n:=0; m:=0;
readln(fin,p); readln(fin,t);
while (ord(p[m+1])<>0) do inc(m);
while (ord(t[n+1])<>0) do inc(n);  
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);
if nr>1000 then nr:=1000;
for i:=1 to nr do write(fout,ap[i],' ');
close(fout);
writeln(m,' ',n);
end.