Trie data structure on dictionary to find rhyming words

Question

I'm working on my function that would find rhyming words from my dictionary text file that contains 40,000 words. For an example, I enter akes and it gives the words printed would be "rakes sakes takes". So, I know it requires data structure with several variables. Maybe bool would be a better declaration for isWord instead of int? So, the function I'm showing is the modified function because the original function could print only 1 word that rhymes with user's input. So therefore, I would need to build the data structre in Trie version. To be honest, I'm pretty awful with data structure so please bear with me.

struct Node
{
    char c;
    Node* letters[26];
    bool isWord;
};

bool findWords(Node*& pTail, char dictionary[][MaxLength + 1], int numberOfDictionaryWords)
{
    Node* pHead;
    pHead = pTail->letters[26];
    bool found = false;
    int first = 0;
    int last = numberOfDictionaryWords - 1;
    int middle = (first + last) / 2;

    while (first <= last)
    {
        if (strncmp(pHead, dictionary[middle], strlen(pTail)) > 0)
        {
            first = middle + 1;
        }
        else if (strncmp(pHead, dictionary[middle], strlen(pTail)) == 0)
        {
            char theWord[MaxLength + 1];
            memcpy(theWord, dictionary[middle], sizeof(char) * (MaxLength + 1));
            cout << "Words(s) found: " << strReverse(theWord) << endl;
            found = true;
            break;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first + last) / 2;
    }
    return found;
}

int the main():

Node* pTail = NULL;
char dictionary[Rows][MaxLength + 1];
int numberOfWords = 0;
readFile(dictionary, numberOfWords);
sortDictionaryInReverse(dictionary, numberOfWords);
char aWord[MaxLength];
cout << "Enter the suffix to find rhyming words: ";
cin >> aWord;
convertToLowerCase(aWord, strlen(aWord));
strReverse(aWord);

if (findWords(aWord, dictionary, numberOfWords))
{
    cout << "This rhyming word is in the dictionary. \n";
}
else
{
    cout << "This rhyming word is not in the dictionary. \n";
}

Answer 1

I think that a std::multimap would be your best bet.

Your non-words would be the keys and the rhyming words would be the values.

So you could set it up like this:

std::multimap<std::string, std::string> foo;

foo.insert(std::make_pair("akes", "rakes"));
foo.insert(std::make_pair("akes", "sakes"));
foo.insert(std::make_pair("akes", "takes"));

If you wanted to say print out all the rhymes of "akes" you could do:

std::cout << "akes\n\t";
for(auto i = foo.equal_range("akes"); i.first != i.second; ++i.first){
    std::cout << i.first->second << ' ';
}

If you wanted to print out just the first element you could do this:

std::cout << "akes " << foo.find("akes")->second;