Pagini recente » Cod sursa (job #950374) | Cod sursa (job #556572) | Cod sursa (job #165705) | Cod sursa (job #859128) | Cod sursa (job #411068)
Cod sursa(job #411068)
{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.