Pagini recente » Cod sursa (job #2115968) | Cod sursa (job #2123016) | Cod sursa (job #471789) | Cod sursa (job #2780170) | Cod sursa (job #1098218)
program algiritmul_KMP_nr_sipoz_aparitiei_uni_subsir_intrun_sir;
type sir=array[1..2000000]of char;
var a,b:sir;
urm,c:array[1..2000000] of 0..2000000;
n,m,q,s,i,j:0..2000000;
f,g:text;
procedure urmatorul(p:sir);
var k:0..2000000;
begin
urm[1]:=0;
k:=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;
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
i:=0; j:=0;
while not seekeoln(f) do begin
inc(i);
read(f,a[i]);
end;
readln(f);
while not seekeoln(f) do begin
inc(j);
read(f,b[j]);
end;
m:=i;
n:=j;
close(f);
urmatorul(a);
q:=0;
j:=0;
for i:=1 to n do begin
while (q>0) and (a[q+1]<>b[i]) do q:=urm[q];
if a[q+1]=b[i] then inc(q);
if q=m then begin j:=j+1;
c[j]:=i-m; q:=urm[q]; end;
end;
writeln(g,j);
for i:=1 to j do write(g,c[i],' ');
close(g);
end.