Pagini recente » Cod sursa (job #2228396) | Cod sursa (job #1287951) | Cod sursa (job #2610751) | Cod sursa (job #1525536) | Cod sursa (job #582040)
Cod sursa(job #582040)
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.