Pagini recente » Cod sursa (job #1670294) | Cod sursa (job #2104172) | Cod sursa (job #2660362) | Cod sursa (job #2378815) | Cod sursa (job #1365789)
program KMP;
var x1,y1,z:ansistring;
pi,d:array[0..2000000] of longint;
x,y:array[1..2000000] of char;
bufin,bufout:array[1..400000] of char;
n,m,i,k,nr:longint;
f,g:text;
procedure construct_pi;
var k,i:longint;
begin
pi[1]:=0;
k:=0;
for i:=2 to n do
begin
while(k>0)and(x[i]<>x[k+1]) do
k:=pi[k];
if x[i]=x[k+1] then
k:=k+1;
pi[i]:=k;
end;
end;
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
settextbuf(f,bufin);
settextbuf(f,bufout);
readln(f,x1);
readln(f,y1);
n:=length(x1);
m:=length(y1);
if n>m then
begin
z:=x1;
x1:=y1;
y1:=z;
end;
for i:=1 to n do
x[i]:=x1[i];
for i:=1 to m do
y[i]:=y1[i];
construct_pi;
k:=0;
for i:=1 to m do
begin
while (k>0)and(y[i]<>x[k+1]) do
k:=pi[k];
if y[i]=x[k+1] then
k:=k+1;
d[i]:=k;
if k=n then
nr:=nr+1;
end;
writeln(g,nr);
k:=0;
for i:=1 to m do
if d[i]=n then
begin
write(g,i-n,' ');
k:=k+1;
if k=1000 then
break;
end;
close(f);
close(g);
end.