Pagini recente » Cod sursa (job #716836) | Cod sursa (job #1687173) | Cod sursa (job #3139797) | Cod sursa (job #913353) | Cod sursa (job #699896)
Cod sursa(job #699896)
program kmp;
const fi='strmatch.in';
fo='strmatch.out';
var f,g:text;
bufin,bufout:array[1..65000] of byte;
urm:array[1..200000] of longint;
v:array[1..1000] of longint;
nr,i,j,k,m,n:longint;
s,t:ansistring;
procedure creare_pref;
begin
k:=0;
urm[1]:=0;
for i:=2 to m do
begin
while (k>0)and(s[i]<>s[k+1]) do
k:=urm[k];
if s[i]=s[k+1] then
inc(k);
urm[i]:=k;
end;
end;
begin
assign(f,fi);
reset(f);
settextbuf(f,bufin);
assign(g,fo);
rewrite(g);
settextbuf(g,bufout);
readln(f,s);
readln(f,t);
m:=length(s);
n:=length(t);
creare_pref;
k:=0;
for j:=1 to n do
begin
while (k>0)and(t[j]<>s[k+1]) do
k:=urm[k];
if t[j]=s[k+1] then
inc(k);
if k=m then
begin
inc(nr);
if nr<1001 then
v[nr]:=j-k;
k:=urm[k];
end;
end;
writeln(g,nr);
if nr>1000 then
nr:=1000;
for i:=1 to nr do
write(g,v[i],' ');
close(f);
close(g);
end.