Same word when missing letters Idea

From a given word dictionary (containing only plain letters, i.e: no accent or other special chars), with a given fixed word length, find every same when a given number letters are missing.

For sample: un--ed could match: united, untied or unused


  Using my dictionnary: /usr/share/dict/american-english, searching for same 6 letters words, having 2 letters missing let me find:
  
  
  19242 different possible combination (shapes),
  The most matching shape is -a-ing, that will match saving, gaming, hating and more than 80 other words
  There is 11209 matching shapes for which only two words match, like -hre-d that would only match shrewd or thread.
  


The goal of this challenge is to write the most efficient algorithm (and implement them in any language) for


extract all given fixed length words from a dictionnary
find all possible multiple words that could be match same shape containing a given fixed number of missing letter.
Sort and present output from the most matching shape to the less matching shape.


There are 3 variables:


Dictionnary file name (could be STDIN)
Fixed words length
Number of missing chars


This could be transmitted in any way you may find usefull.

Samples

A quick sample could better explain: Searching for same shape of 18 letters, having 2 missing letters give only one match:

same /usr/share/dict/american-english 18 2
electrocardiogra--: electrocardiograms,electrocardiograph


or

same /usr/share/dict/american-english 8 2
17: --ddling: coddling,cuddling,diddling,fiddling,fuddling,huddling,meddling,middling,muddling,paddling,peddling,piddling,puddling,riddling,saddling,toddling,waddling
17: -us-iest: bushiest,cushiest,duskiest,dustiest,fussiest,fustiest,gushiest,gustiest,huskiest,lustiest,mushiest,muskiest,mussiest,mustiest,pushiest,pussiest,rustiest
16: --tching: batching,bitching,botching,catching,ditching,fetching,hatching,hitching,latching,matching,notching,patching,pitching,retching,watching,witching
15: sta--ing: stabbing,stabling,stacking,staffing,staining,stalking,stalling,stamping,standing,stapling,starling,starring,starting,starving,stashing
15: --ttered: battered,bettered,buttered,fettered,guttered,lettered,littered,mattered,muttered,pattered,pottered,puttered,tattered,tittered,tottered
...
 2: -e-onate: detonate,resonate
 2: c-mmune-: communed,communes
 2: trou-le-: troubled,troubles
 2: l-t-rals: laterals,literals
 2: sp-ci-us: spacious,specious
 2: -oardi-g: boarding,hoarding
 2: pre-ide-: presided,presides
 2: blen-he-: blenched,blenches
 2: sw-llin-: swelling,swilling
 2: p-uc-ing: plucking,pouching


or


  The shape ---l- match hello and world as well as 297 other words.:

same /usr/share/dict/american-english 5 4 |
    sed -ne '/hello/{s/^ *\([0-9]*: [a-z-]*\):.*,world,.*$/\1/p}'
299: ---l-



Test file

For testing, I've posted this 62861 length extract from my dict file in plain ascii, useable from jsfiddle, jsbin or even from your filesystem (because of the directive access-control-allow-origin) ( sample: @edc65 answer, with score count ).

Ranking

This is a fastest algorithm challenge.

The goal of this is to find quickest way for building shape, making comparissions and sorting list.

But the natural speed of language have to not be matter. So if a solution using bash is slower, but simplier, using more efficient algorithm than another c based solution, the simplier (maybe slower) have to win.

The score is the number of logical steps required by the whole job, using any dictionary file (my personal english dictionary: wc -l /usr/share/dict/american-english -&gt; 99171) and different combinations of word length and number of missing letters.

The lowest score win.
C++11


Excuse the variable names.

Calculates hamming distance between each pair of words then tries replacing characters in words with '-', and calculates hamming distance between the word with '-' and the words without (that had a low enough hamming distance). See comments for details.

#include &lt;algorithm&gt;
#include &lt;cassert&gt;
#include &lt;cstdio&gt;
#include &lt;fstream&gt;
#include &lt;ios&gt;
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;string&gt;
#include &lt;utility&gt;
#include &lt;vector&gt;

// Calculates hamming distance between a and b, both of which are length m
inline int fries(const std::string &amp;a, const std::string &amp;b, int m){
    int c = 0;
    for(int i = 0; i &lt; m; ++i)
        a[i]==b[i] || ++c;
    return c;
}
using namespace std;

int main(int eggs, char **bagels){
    ios_base::sync_with_stdio(false);
    // make sure proper number of arguments are passed
    assert(eggs == 4);

    int m, k;
    // read in m (word length) and k (number of '-'s)
    sscanf(bagels[2], "%i", &amp;m);
    sscanf(bagels[3], "%i", &amp;k);

    // bacon will store all words that are of length m
    vector&lt;string&gt; bacon;
    bacon.reserve(500000);

    // Save only words that are of length m
    ifstream milk(bagels[1]);
    {
        string toast;
        while(getline(milk, toast))
            if(toast.length() == m)
                bacon.push_back(toast);
    }

    // ham[i] will store the indices of strings with a hamming distance from bacon[i] that is at most k
    vector&lt;vector&lt;int&gt;&gt; ham(bacon.size());

    // Calculate hamming distance, if &lt;=k, add to ham. 
    for(int i = 0, sz = bacon.size(); i &lt; sz; ++i){
        // Uses i+1 to ensure each PAIR is only checked once
        for(int j = i+1; j &lt; sz; ++j){
            unsigned strip = fries(bacon[i], bacon[j], m);
            if(strip &amp;&amp; strip &lt;= k)
                ham[i].push_back(j);
        }
    }

    // cereal[string], where string is the matching shape, and the vector is a vector of indices of strings that are matched by string
    map&lt;string, vector&lt;int&gt;&gt; cereal;
    for(int i = 0, sz = ham.size(); i &lt; sz; ++i){
        // skip words that are not similar enough to other words
        if(ham[i].size() == 0) continue;

        // Iterate through all versions of bacon[i] with k '-'s
        // THIS ONLY ITERATES THROUGH COMBINATIONS NOT PERMUTATIONS
        vector&lt;bool&gt; cream(m);
        fill(cream.begin()+k,cream.end(),true);
        do{
            std::string juice = bacon[i];
            // Add in '-'s
            for(int i = 0; i &lt; m; ++i){
                if(!cream[i]) juice[i] = '-';
            }
            // Ensure that this pattern has not yet been processed
            if(!cereal.count(juice)){
                // For each of the words with hamming distance&lt;=k, check hamming distance with the matching shape
                // If hamming distance == k, then it matches, so save to cereal
                for(int j = 0, ssz = ham[i].size(); j &lt; ssz; ++j){
                    if(fries(juice, bacon[ham[i][j]], m) == k)
                        cereal[juice].push_back(ham[i][j]);
                }
                // In the case that there ARE matches, put the index of the original string at the end
                if(cereal.count(juice))
                    cereal[juice].push_back(i);
            }
        }while(next_permutation(cream.begin(), cream.end()));
    }
    // Sorts all the matching shapes by number of matches
    vector&lt;pair&lt;string, vector&lt;int&gt;&gt;&gt; orange_juice;
    copy(cereal.begin(), cereal.end(), back_inserter(orange_juice));
    sort(orange_juice.begin(), orange_juice.end(), [](const pair&lt;string, vector&lt;int&gt;&gt; &amp;a, const pair&lt;string, vector&lt;int&gt;&gt; &amp;b){
        return a.second.size() &gt; b.second.size();
    }); 
    // Iterate through sorted matching shapes, print
    for(auto cake:orange_juice){
        // bacon[cake.second.back()] is the original string from which the pattern was derived
        cout &lt;&lt; cake.second.size() &lt;&lt; ": " &lt;&lt; cake.first &lt;&lt; ": " &lt;&lt; bacon[cake.second.back()];
        // do not print original string twice
        cake.second.pop_back();
        // print other strings
        for(auto coffee:cake.second){
            cout &lt;&lt; "," &lt;&lt; bacon[coffee];
        }
        cout &lt;&lt; "\n";
    }
    return 0;
}