Cod sursa(job #328471)

Utilizator levap1506Gutu Pavel levap1506 Data 2 iulie 2009 11:16:00
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.05 kb
program strmatch;
 var a,b:text;
  i,j,k,m,n,q:longint;
  z,x:array[1..2000000] of char;
  pi:array[0..2000000] of longint;
  match:array[1..1000] of longint;
   begin
    assign(a,'strmatch.in');
    assign(b,'strmatch.out');
    reset(a);
    rewrite(b);
    while not(eoln(a)) do
     begin
      i:=i+1;
      Read(a,z[i]);
     end;
    Readln(a);
    while not(eoln(a)) do
     begin
      j:=j+1;
      Read(a,x[j]);
     end;
    m:=i;
    n:=j;
     k:=0;
     pi[1]:=0;
     for i:=2 to m do
      begin
       while (k>0) and (z[k+1]<>z[i]) do
         k:=pi[k];
       if z[k+1]=z[i] then
         k:=k+1;
       pi[i]:=k;
      end;
     q:=0;
     k:=0;
     for i:=1 to n do
      begin
       while (q>0) and (z[q+1]<>x[i]) do
         q:=pi[q];
       if z[q+1]=x[i] then
         q:=q+1;
       if q=m then begin q:=pi[m]; inc(k); if k<1001 then match[k]:=i-m; end;
      end;
      Writeln(b,k);
      if k>1000 then k:=1000;
      for i:=1 to k do
       Write(b,match[i],' ');
       close(b);
   end.