Cod sursa(job #411047)

Utilizator hungntnktpHungntnktp hungntnktp Data 4 martie 2010 18:22:23
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.18 kb
{DINH QUANG DAT TIN 07-10}
{STRMATCH}
{$inline on}
{$mode objfpc}
CONST
 TFI='strmatch.in';
 TFO='strmatch.out';
 MAX=3000001;
TYPE
 arr1int=array[0..MAX] of longint;
VAR
 fi,fo:text;
 cnt,m,n:longint;
 res,next:arr1int;
 a,b:ansistring;

PROCEDURE       input;
begin
 assign(fi,tfi);reset(fi);
  readln(fi,a);
  readln(fi,b);
 close(fi);
end;

PROCEDURE       init;
begin
 m:=length(a);
 n:=length(b);
 cnt:=0;
end;

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

PROCEDURE       process;inline;
var
 j,i:longint;
begin
 prepare;
 i:=1;
 j:=1;
 while j<=n do
  begin
   while (i>0) and (a[i]<>b[j]) do i:=next[i];
   inc(i);
   inc(j);
   if i>m then
    begin
     inc(cnt);
     res[cnt]:=j-i;
     i:=next[i];
    end;
  end;
end;

PROCEDURE       output;
var
 i:longint;
begin
 assign(fo,tfo);rewrite(fo);
  writeln(fo,cnt);
  for i:= 1 to cnt do write(fo,res[i],' ');
 close(fo);
end;

BEGIN
 input;
 init;
 process;
 output;
END.