in reply to minimal superstrings/maximal substrings
The best algorithm depends on your data's size, because a complex algorithm doesn't pay off when only being some seconds faster.
My take on it is to first sort and partition your words in subsets of same length, because every "cover word" must have more letters.
Start by putting all words of the first partition into @uncovered and test them against all words of the next partition.
For each match you'll store into a hash $cover{$smaller}=$bigger and delete $smaller from @uncovered.
Then you'll push the @current_partition to the remaining words in @uncovered and repeat with the next partition.
This is a generic algorithm, your case with 9 up and 8 down can be easily adopted.