Pagini recente » Cod sursa (job #2393453) | Cod sursa (job #2089242) | Cod sursa (job #328773) | Cod sursa (job #849921) | Cod sursa (job #1365783)
program kmp;
var x,y:ansistring;
bufin,bufout:array[1..4000002] of byte;
d,pi:array[1..255] of integer;
nr,i,k,n,m:longint;
begin
assign(input,'strmatch.in'); reset(input);
assign(output,'strmatch.out'); rewrite(output);
settextbuf(input,bufin);
settextbuf(output,bufout);
readln(x);
readln(y);
n:=length(x);
m:=length(y);
k:=0;
pi[1]:=0;
for i:=2 to n do
begin
while (k>0) and (x[i]<>x[k+1]) do
k:=pi[k];
if x[i]=x[k+1] then
inc(k);
pi[i]:=k;
end;
k:=0;
nr:=0;
for i:=1 to m do
begin
while (k>0) and (y[i]<>x[k+1]) do
k:=pi[k];
if y[i]=x[k+1] then
inc(k);
d[i]:=k;
if d[i]=n then inc(nr);
end;
writeln(nr); nr:=0;
for i:=1 to m do
if d[i]=n then
begin
if nr<=1000 then write(i-n,' ')
else break;
inc(nr);
end;
close(input); close(output);
end.