Create a program that solves word anagrams using a hash table. Here's how to do it...

First make an AnagramSet class that stores a set of anagramatic words along with a key formed by sorting letters in alphabetical order.

For example, suppose abets, bates, betas, beast, baste, besat, tabes, beats, sebat are all in valid words. Then our AnagramSet would be the key value pair

< "abest", { abets, baste, bates, beast, beats, besat, betas, sebat, tabes } >

To store the word sets you can use an array, vector , OList or the STL set class.

Your hash table will be an array of size 50,000 with elements of type vector .

The hash function will map AnagramSet keys to array indexes.

For example if hash("abest") = 3429 then you will store the AnagramSet for "abest" at index 3429. To be more precise, you'll store the AnagramSet in the vector at that index.

Using vectors as the array elements will allow for collisions e.g. if hash("ehllo") also maps to 3429 then we would push the AnagramSet with key "ehllo" onto the same vector. We are using separate chaining here where the chains are vectors rather than linked lists.

Use the file words(1).txt to populate the hash table. Every time you read in a word (e.g. "hello") from the file, make a key (e.g. "ehllo"), hash the key e.g. (hash("ehllo") --> 3429), and go to the chain at that index in the hash table. If the chain contains an AnagramSet with that key, insert your word into the AnagramSet. Otherwise create a new AnagramSet with the key (e.g. <"ehllo", { "hello" } >) and push it on the chain.

Once the hash table is populated, the program will prompt the user for words to "unscramble". The user will enter a string and the program will find all words that use the same letters, possibly in a different order. For example, if the user entered "bstae" then the program would say something like "I found 9 words with those letters: abets,baste, bates, beast, beats, besat, betas, sebat, tabes. Let the user continue entering strings until they want to quit.

Upload your program to BB. Your upload doesn't have to be a Visual Studio project this time. Just be sure to upload all the file necessary to compile the program.

Also upload a screenshot (e.g. a jpeg) of a sample run where the program is used to unscramble several words including "bstae " and other strings with multiple anagramatic forms.

Provide member functions printMatches, contains, removeWord and insertWord so your hashTable class will work with the client code below.

do {

cout << "Enter a string or q to quit: ";

cin >> s;

if (s != "q") {

myTable.printMatches(s);

string response;

if (!myTable.contains(s)) {

cout << "Do you want to add \"" << s << "\" to the table? (y/n) ";

cin >> response;

if (response == "y") myTable.insertWord(s);

}

else {

cout << "Do you want to remove \"" << s << "\" from the table? (y/n) ";

cin >> response;

if (response == "y") myTable.removeWord(s);

}

}

} while (s != "q");

Enter a string or q to quit: hello

{ hello }

Do you want to remove "hello" from the table? (y/n) y

Enter a string or q to quit: hello

{ }

Do you want to add "hello" to the table? (y/n) y

Enter a string or q to quit: hello

{ hello }

Do you want to remove "hello" from the table? (y/n) n

Enter a string or q to quit: olleh

{ hello }

Do you want to add "olleh" to the table? (y/n) y

Enter a string or q to quit: olleh

{ hello, olleh }

Do you want to remove "olleh" from the table? (y/n) n

Enter a string or q to quit: racse

{ acers, acres, cares, carse, races, scare, scrae, serac }

Do you want to add "racse" to the table? (y/n) n

Enter a string or q to quit: fdsafdsafd

{ }

Do you want to add "fdsafdsafd" to the table? (y/n) y

Enter a string or q to quit: fdsafdsafd

{ fdsafdsafd }

Do you want to remove "fdsafdsafd" from the table? (y/n) n

Enter a string or q to quit: aadddfffss

{ fdsafdsafd }

Do you want to add "aadddfffss" to the table? (y/n) y

Enter a string or q to quit: dddaafffss

{ fdsafdsafd, aadddfffss }

Do you want to add "dddaafffss" to the table? (y/n) n

Enter a string or q to quit: cat

{ act, cat }

Do you want to remove "cat" from the table? (y/n) y

Enter a string or q to quit: act

{ act }

Do you want to remove "act" from the table? (y/n) y

Enter a string or q to quit: tac

{ }

Do you want to add "tac" to the table? (y/n) y

Enter a string or q to quit: tac

{ tac }

Do you want to remove "tac" from the table? (y/n) n

Enter a string or q to quit: q