Cod sursa(job #411068)

Utilizator hungntnktpHungntnktp hungntnktp Data 4 martie 2010 18:30:48
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.24 kb
{DINH QUANG DAT TIN 07-10}
{KMP}
{$H+,R-}
{$mode objfpc}
{$inline on}
CONST
 TFI='strmatch.in';
 TFO='strmatch.out';
 MAX=2000007;
TYPE
 integer=longint;
 arr1int=array[0..MAX] of longint;
VAR
 fi,fo:text;
 cnt,m,n:integer;
 x,y:string;
 res,next:arr1int;

PROCEDURE       input;
begin
 assign(fi,tfi);reset(fi);
  readln(fi,x);
  readln(fi,y);
 close(fi);
end;

PROCEDURE       init;
begin
 n:=length(y);
 m:=length(x);
 cnt:=0;
end;

PROCEDURE       prepare;   inline;
var
 i,j,k:integer;
begin
 i:=1;
 j:=0;
 next[1]:=0;
 while (i<=m) do
  begin
   while (j>0) and (x[i]<>x[j]) do j:=next[j];
   inc(i);
   inc(j);
   if x[i]=x[j] then next[i]:=next[j]
    else next[i]:=j;
  end;
end;

PROCEDURE       process;inline;
var
 i,j:integer;
begin
 prepare;
 i:=1;
 j:=1;
 while j<=n do
  begin
   while (i>0) and (x[i]<>y[j]) do i:=next[i];
   inc(i);
   inc(j);
   if i>m then
    begin
     if cnt<1000 then
      begin
       inc(cnt);
       res[cnt]:=j-i;
       if cnt=1000 then exit;
      end;
     i:=next[i];
    end;
  end;
 writeln(fo,cnt);
 for i:= 1 to cnt do write(fo,res[i],' ');
end;

BEGIN
 assign(fo,tfo);rewrite(fo);
 input;
 init;
 process;

 close(fo);
END.