

sub min_chunks {
  $_ = lc $_ for my ($s1, $s2) = @_;
  # Specifications say to assume anagrams, but let's be explicit:
  die "Same words (not anagrams)" if $s1 eq $s2;
  die "Not anagrams"
    if join('',sort split//,$s1) ne join('',sort split//,$s2);
  my @s = _min_chunks($s1, $s2, 1+length($s1));
  return scalar @s;
}

sub _min_chunks {
  my ($s1, $s2, $best) = @_;
  my @best;
OUTER:
  for my $i (reverse 1 .. (length($s1)-1)) {
    my $chunk = substr($s1, 0, $i);
    my $pos=-1;
  INNER:
    while (($pos=index($s2, $chunk, $pos+1))>=0) {
      my $remains2 = $s2;
      substr($remains2, $pos, $i) = ' ';
      my @junk = split' ', $remains2; # blah ... I just need the count ...
      next INNER if $best <= 1+@junk;
      $remains2 =~ s/^ +//;
      $remains2 =~ s/ +$//;
      my $remains1 = substr($s1, $i);
      return ($chunk, $remains1) if $remains1 eq $remains2;
      my @try = _min_chunks($remains1, $remains2, $best);
      next INNER unless @try;
      next INNER if $best <= 1+@try;
      $best = @best = ($chunk, @try);
      # Try to find out if @best is optimal ...
      for my $i1 (0 .. $#best-1) {
        # Pathological cases might trigger this "pessimization" ...
        # like qw( aaaaaaaaaaaaaaabobbibbub bubbibbobaaaaaaaaaaaaaaa ) ...
        # (anyone have any idea how to avoid that?)
        next INNER if index($s2, substr($best[$i1],  -1) .
                                 substr($best[$i1+1], 0, 1)) >= 0;
      }
      last OUTER; # ... but if we got here, @best is surely optimal.
    }
  }
  return @best;
}

min_chunks('xylinid', 'xylidin');
