Problem Statement:
Program that reads a file containing a sorted list of words (one word per line, no spaces, all lower case), then identifies the longest word in the file that can be constructed by concatenating copies of shorter words also found in the file. The program should then go on to report the second longest word found as well as how many of the words in the list can be constructed of other words in the list.”
For a better understanding the example:
The following strings :
animal
game
develop
animalgame
animalgamedevelop
rat
cat
ratgame
expected output:
Longest word would be: animalgamedevelop
Second longest would be animalgame
The count of the words formed by other words : 3
I have implemented the trie data structure and took a recursive approach to solve the problem. I have also timed my algorithm about how long it takes. I have also added an automated test case which runs every time the user runs the executable to follow good practices.
The input file is a big data set which contains about 1735531 strings altogether.
The data set in this link:
Source Code Header file