You may be able to use substr and length to accomplish this task much faster:

chomp $key; # don't care about trailing newline, if any.
foreach my $combine (keys %$self) {
  if (substr($key, 0, length $combine) eq $combine) {
    print "Found (prefix $combine): ", substr ($key, length $combine),
+ "\n";
  }
  if (substr($key, -length $combine) eq $combine) {
    print "Found (suffix $combine): ",
      substr ($key, 0, length($key) - length $combine), "\n";
  }
}
[download]

This should avoid the overhead of compiling a regex, and the overhead of index (or rindex) searching in more places in the string then are needed.

It will of course not work if you want regex-type searching, of the keys of %$self.

I think that unless you could have your keys stored already ordered, it is likely that sorting overhead would outway any advantage gained through a binary search, etc.