Cod sursa(job #328466)

Utilizator levap1506Gutu Pavel levap1506 Data 2 iulie 2009 10:58:04
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 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..400000] 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
         if k<1000 then begin inc(k); match[k]:=i-m; end else inc(k);end;
      end;
      Writeln(b,k);
      for i:=1 to k do
       Write(b,match[i],' ');
       close(b);
   end.