Pagini recente » Cod sursa (job #2144071) | Cod sursa (job #1746340) | Cod sursa (job #2310060) | Cod sursa (job #2483883) | Cod sursa (job #299480)
Cod sursa(job #299480)
Program kmp;
type vec=array[0..256] of integer;
poz=array[1..1000] of integer;
var s,x: string;
i: integer;
c: poz;
Function prefix(x: string): vec;
var m,k,i: longint;
v: vec;
begin
m:=length(x);
v[1]:=0;
k:=0;
for i:=2 to m do
begin
while(k>0) and (x[k+1]<>x[i]) do
k:=v[k];
if x[k+1]=x[i] then k:=k+1;
v[i]:=k;
end;
prefix:=v;
end;
Procedure KMP(s,x: string);
var m,n,i,j,q,p: longint;
v: vec;
begin
n:= length(s);
m:=length(x);
v:=prefix(x);
q:=0;
p:=0;
for i:=1 to n do
begin
while (q>0) and (x[q+1]<>s[i]) do
q:=v[q];
if x[q+1]=s[i] then q:=q+1;
if q=m then
begin
if p<1000 then
begin
p:=p+1;
c[p]:=i-m;
end
else break;
q:=v[q];
end;
end;
end;
begin
assign(t,'strmatch.in'); reset(t);
read(t,s);
readln(t);
read(t,x);
close(t);
KMP(s,x);
assign(t,'strmatch.out'); rewrite(t);
writeln(t,p);
for i:=1 to p do
write(t,c[i],' ');
close(t);
end.