Pagini recente » Cod sursa (job #3151094) | Cod sursa (job #2626680) | Cod sursa (job #156231)
Cod sursa(job #156231)
//Knuth Morris Pratt
const nmax=2000000;
var fi,fo:text;
n,m,i,k,x,ct:longint;
T,P:ansistring;
Next,sol:array[0..nmax]of longint;
begin
assign(fi,'strmatch.in'); reset(fi);
assign(fo,'strmatch.out'); rewrite(fo);
readln(fi,P); readln(fi,T);
n:=length(T); m:=length(P);
Next[1]:=0; k:=0;
for i:=2 to m do
begin
while (k>1)and(P[k+1]<>P[i]) do
k:=Next[k];
if P[k+1]=P[i] then inc(k);
Next[i]:=k;
end;
x:=0; ct:=0;
for i:=1 to n do
begin
while (x>1)and(P[x+1]<>T[i]) do x:=Next[x];
if P[x+1]=T[i] then inc(x);
if x=m then
begin
inc(ct);
if ct<=1000 then sol[ct]:=i-m;
x:=Next[x];
end;
end;
writeln(fo,ct);
if ct>1000 then ct:=1000;
for i:=1 to ct do
write(fo,sol[i],' ');
close(fi);
close(fo);
end.