ah! i saw this last night and i started mumbling around a lot of permutations of regexes.. but my brain was too little to afford it.
Then, before sleeping, a simpler solution (regex based) come to my mind.
I'm not a Perl golfer at all and i cant even read the proposed solution: so i answer to the challenge part of the question. Anyway my Perl tends to be unreadable, so my simple solution is quite obfu..

But, in the example you gave using the 'mig' pattern, Corion, the resulting ranking of choices ( migrations django_migrations main_generator django_admin_log ) is equal to the last one in the python example, but i dont understand why 'django_migrations' comes before 'main_generator': maybe i'm wrong but in my mind 'shortest leftmost' means 'leftmost shortest' and this is the normal way to order strings..

Here is my nine lines (of relevant code) solution, using plain Perl (i'm sure it can be shortened and golfed a lot..). It handles also the correct order of similar words:

#!perl
use strict;
use warnings;

@ARGV=qw(mig main_generator migrations django_migrations django_admin_
+log myfoo\bar.txt main_generatorZ XXX xxx);

my $patt = shift;
my $rx = (map {qr/$_/} join '', (map { '([^'.$_.']*)(?:'.$_.')'} $patt
+=~/./g ))[0] ;
my %r;
map {
    $_=~/$rx/ ?
    push @{$r{join'_', map{sprintf "%02d",length $_} $_=~/$rx/g}},$_ :
    push @{$r{join'_', map{'99'} 1..length $patt}} ,$_
}@ARGV;
print map { join ' ', sort @{$r{$_}},"\n" } sort keys %r;


__OUT__

 migrations
 main_generator main_generatorZ
 django_migrations
 django_admin_log
 XXX myfoo\bar.txt xxx
[download]

L*