This project will be three parts. Part I is to construct a Trie using a dictionary file provided. Part II is to implement a command-line search auto complete interface. Please note that you need to implement your own version of Trie. Part III is to implement a recommendation search. You cannot use existing C++ library Trie or use an implementation online. Points will be taken off otherwise.

Part I (45 points):

Dictionary. txt is provided to you to construct the Trie. Each line contains a valid search query. Your task is to insert these queries into your Trie. Implement trie classes for part 1.

Part II (45 points):

Using the Trie class completed in Part I, create a C++ program that takes an user input and output auto completion options. The interface should be similar to the following:

$> Please type search queries:

$> binary sea

$> Your options are:

$> binary search

$> binary search tree

$> binary search tree java

Implement a search. cpp file to complete part II

Part III (10 points):

Implement a recommendation search. When you search a term that is not in the Trie, recommend the top 3 most similar entries in the Trie:

$> Please type search queries:

$> cakr

$> Do you mean:

$> cake

$> cat

$> crack

*I was unable to attach the dictionary. txt file, but it looks similar to what I have pasted below:

aaa
aaas
aactive
aadvantage
aaker
aap
aapg
aaron
aarp
aas
aau
ab1890
ab1x
ab31x
aba
abacus
abag
abalone
abandon
abandoned
abandoning
abandonment
abate
abated
abb
abbott
abbreviated
abbreviation
abby
abc
abcm
abdullah