Cod sursa(job #1098221)

Utilizator sulzandreiandrei sulzandrei Data 4 februarie 2014 17:39:57
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.95 kb
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);
 if j>1000 then j:=1000;
 for i:=1 to j do write(g,c[i],' ');
 close(g);
end.