Cod sursa(job #358047)

Utilizator philipPhilip philip Data 21 octombrie 2009 19:01:07
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.12 kb
var f,g:text;
    a,b:array [1..2000001] of char;
    pi:array[1..2000001] of longint;
    c:array[1..1001] of longint;
    i,j,m,n,k,s,q:longint;

procedure citire;
  begin
    assign(f,'strmatch.in');
    reset(f);
    n:=0;
    m:=0;
    while not eoln(f) do begin
      m:=m+1;
      read(f,b[m]);
    end;
    readln(f);
    while not eoln(f) do begin
      n:=n+1;
      read(f,a[n]);
    end;
    close(f);
  end;


procedure afisare;
  begin
    assign(g,'strmatch.out');
    rewrite(g);
      writeln(g,s);
      if s>1000 then for i:=1 to 1000 do write(g,c[i],' ')
        else for i:=1 to s do write(g,c[i],' ');
    close(g);
  end;


begin
  citire;
  k:=0;
  pi[1]:=0;

  for i:=2 to m do
    begin
      while (k>0) and (b[k+1]<>b[i]) do
        k:=pi[k];
      if b[k+1]=b[i] then
        k:=k+1;
      pi[i]:=k;
    end;

  q:=0;
  for i:=1 to n do
    begin
      while (q>0) and (b[q+1]<>a[i]) do
        q:=pi[q];
      if b[q+1]=a[i] then
        q:=q+1;
      if q=m then begin
        s:=s+1;
        if s<1001 then c[s]:=i-m;
      end;
    end;
  afisare;
end.