Yes, of course. I'd totally missed the point of returning an array! This will solve that part:

sub tony_UCS {
  local $_ = reverse shift;
  my %longest; my $longest = 0; my $tohere = "";
  while (my $char = chop $_) {
    my $idx = index($tohere, $char);
    if ($idx != -1) {
      push @{$longest{$longest = length $tohere}}, $tohere
        if (length $tohere >= $longest);
      $tohere = substr($tohere, $idx + 1) . $char;
    } else {
      $tohere .= $char;
    }
  }
  push @{$longest{$longest = length $tohere}}, $tohere
    if (length $tohere >= $longest);
  return @{$longest{$longest}};
}
[download]

It's still considerably faster than the original, even if not O(n). :)

Tony