255 characters, minus four for newlines. I could cut it down at least to 243 if it doesn't need -w and strict.
It's not beautiful, but it's much nicer than my first attempt:
sub assemble{my($f,$s)=splice(@_,0,2);return$f unless$s;
$f=(sort{length($a)<=>length($b)}(c($f,$s),c($s,$f)))[0];
assemble($f,@_)}
sub c{($_,$b)=@_;return$_ if/$b/;my $r='';while($b and$r=chop($b).$r
and!(index($_,$b)>0)){}$_.$r.(length($b)==1?$b:'')}
Update: I see what the problem is. Luckily, a fix is even shorter. Here's one at 246 characters, minus four newlines. Removing -w and strict would put me around 230:
sub assemble{my($f,$s)=splice(@_,0,2);return$f unless$s;
$f=(sort{length($a)<=>length($b)}(c($f,$s),c($s,$f)))[0];
assemble($f,@_)}
sub c{($_,$b)=@_;return$_ if/$b/;my $r='';while($b and$r=chop($b).$r
and!(index($_,$b)>0)){}$_.$r.(/$b$/?'':$b)}