Update: Fixed. As Jenda observed, my original solution solved a problem other than the one presented.

O(N*log(N) + N*(M + M³) + M)
= O(N*log(N) + N*M³)
N = number of words.
M = length of words.

Don't let the M³ scare you. Benchmark them to find out which is best for you.

use strict;
use warnings;

my @data = qw/a mnk ab m b bc abcd cd bcd bd m nk /;

@data = sort { length($a) <=> length($b) } @data;

my %result;

foreach my $word (@data) {
   my $uc_word = uc($word);
   my $partial_word;

   foreach my $start_letter (1..length($uc_word)) {
      foreach my $num_letters ($start_letter..length($uc_word)-$start_
+letter+1) {
         delete($result{substr($uc_word, $start_letter-1, $num_letters
+)});
      }
   }

   $result{$uc_word} = $word;
}


print join(",", values(%result));
[download]