Same word when missing letters
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;
}