Pagini recente » Cod sursa (job #73741) | Cod sursa (job #3280616) | Cod sursa (job #918179) | Cod sursa (job #1023371) | Cod sursa (job #932947)
Cod sursa(job #932947)
program kmp;
var f,g:text;
a,b:ansistring;
n,m,i:longint;
k:longint;
nr:longint;
v:array[1..200000] of longint;
x:array[1..200000] of longint;
bufin,bufout:array[1..65000] of byte;
procedure prefix;
var k:longint;
begin
k:=0; x[1]:=0;
for i:=2 to n do
begin
while (k>0) and (a[i]<>a[k+1]) do
k:=x[k];
if a[i]=a[k+1] then inc(k);
x[i]:=k;
end;
end;
begin
assign (f,'strmatch.in'); reset (f);
assign (g,'strmatch.out'); rewrite (g);
settextbuf (f,bufin);
settextbuf (g,bufout);
readln (f,a);
read (f,b);
n:=length(a);
m:=length(b);
prefix;
k:=0;
for i:=1 to m do
begin
while (k>0) and (b[i]<>a[k+1]) do
k:=x[k];
if b[i]=a[k+1] then
inc(k);
if k=n then
begin
inc(nr);
if nr<1001 then
v[nr]:=i-k;
k:=x[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.