Cod sursa(job #582035)

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

begin
assign (f, 'strmatch.in'); reset (f);
assign (g, 'strmatch.out'); 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;

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];
  if a[k+1]=a[q] then inc(k);
  urm[q]:=k;
  inc(q);
  end;

q:=1; k:=0;
while q<=n do
  begin
  while (k>0) and (b[q]<>a[k+1]) do k:=urm[k];
  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;
for i := 1 to t do write (g, rez[i], ' ');

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