Cod sursa(job #358054)

Utilizator philipPhilip philip Data 21 octombrie 2009 19:18:21
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.27 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:longint;
    q:string;


procedure citire;
  begin
    assign(f,'strmatch.in');
    reset(f);
    n:=0;
    m:=0;
    while not eoln(f) do begin
      read(f,q);
      for i:=1 to length(q) do begin
        m:=m+1;
        b[m]:=q[i];
      end;
    end;
    readln(f);
    while not eoln(f) do begin
      read(f,q);
      for i:=1 to length(q) do begin
        n:=n+1;
        a[n]:=q[i];
      end;
    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;

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