Cod sursa(job #582040)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 14 aprilie 2011 20:17:30
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.44 kb
var urm:array[1..2000000] of longint;
    buf1, buf2:array[1.. 1 shl 17] of char;
    a, b:array[0..2000000] of char;
    rez:array[1..2000000] of longint;
    i, k, q, m, n, t:longint;
    f, g:text;

//a-sirul ce trebuie gasit, avand ca lungime pe m
//b-sirul in care se cauta, avand ca lungime pe n
//t-Numarul total de aparitii
//urm-vectorul lungimii celui mai lung sufix comun


begin
assign (f, 'strmatch.in'); settextbuf(f, buf1); reset (f);
assign (g, 'strmatch.out');settextbuf(f, buf2); rewrite (g);

m:=0;
while not eoln (f) do begin inc(m); read (f, a[m]); end;
readln (f);
n:=0;
while not eoln (f) do begin inc(n); read (f, b[n]); end;

//Crearea vectorului urm
k:=0; urm[1]:=0;
q:=2;
while q<=m do
  begin
  while (k>0) and (a[k+1]<>a[q]) do k:=urm[k];     //Cat timp nu se potrivesc litere, scade lungimea sufixului comun
  if a[k+1]=a[q] then inc(k);                      //Daca s-a gasit litera creste lungimea sufixului comun
  urm[q]:=k;
  inc(q);
  end;

//Cautarea aparitiilor
q:=1; k:=0;
while q<=n do
  begin
  while (k>0) and (b[q]<>a[k+1]) do k:=urm[k];     //Ideea este identica cu cea pentru aflarea celui mai lung sufix
  if b[q]=a[k+1] then inc(k);
  if k = m then begin inc (t); rez[t]:=q-k; end;
  inc(q);
  end;

writeln (g, t);
if t>1000 then t:=1000;                     //Se afiseaza doar primele 1000 de aparitii
for i := 1 to t do write (g, rez[i], ' ');

close (f); close (g);
end.