I cannot even begin to fully fathom what your attempting but it appears your algorithm has some type of odd dependency on the order of the keys. If I change,

foreach my $str (sort {($substrings{$b}[1]-$substrings{$b}[0]) <=> ($s
+ubstrings{$a}[1]-$substrings{$a}[0]) || $substrings{$a}[0] <
=> $substrings{$b}[0]}  keys %substrings){
[download]

foreach my $str (sort {($substrings{$b}[1]-$substrings{$b}[0]) <=> ($s
+ubstrings{$a}[1]-$substrings{$a}[0]) || $substrings{$a}[0] <
=> $substrings{$b}[0]} sort keys %substrings){
[download]

Update: Yikes! scratch all of that except, I cannot even begin to fully fathom. There is something wrong with the sort (as pointed out by kyle).