Pagini recente » Cod sursa (job #2520953) | Cod sursa (job #39594) | Cod sursa (job #2262061) | Cod sursa (job #196915) | Cod sursa (job #2405500)
program kmp;
type sir=array[0..2000000] of char;
tabel=array[0..2000000] of longint;
var a,b:sir;
urm,pos:tabel;
n,m,r,i:longint;
c:char;
procedure scanf(var s:sir; var n:longint);
begin
while not eoln do begin
read(c);
inc(n);
s[n]:=c;
end;
end;
procedure prefix();
var i,k:longint;
begin
urm[1]:=0;
k:=0;
for i:=2 to n do begin
while (k>0) and (a[i]<>a[k+1]) do k:=urm[k];
if (a[i]=a[k+1]) then inc(k);
urm[i]:=k;
end;
end;
procedure kmp();
var i,k:longint;
begin
k:=0;
for i:=1 to m do begin
while (k>0) and (b[i]<>a[k+1]) do k:=urm[k];
if (b[i]=a[k+1]) then inc(k);
if (k=n) then begin
inc(r);
if (r<1000) then pos[r]:=i-n;
k:=urm[k];
end;
end;
end;
begin
assign(input,'strmatch.in');
assign(output,'strmatch.out');
reset(input);
rewrite(output);
scanf(a,n);
readln;
scanf(b,m);
prefix();
kmp();
writeln(r);
if r>1000 then r:=1000;
for i:=1 to r do write(pos[i],' ');
close(input);
close(output);
end.