Question
This question needs to be solved with trie data structure in java. Thank you for your effort. You are not allowed to use any external
This question needs to be solved with trie data structure in java. Thank you for your effort.
You are not allowed to use any external library or .jar file.
You are expected to implement Trie data structure and following functions. Firstly, you should create a Trie data structure, and then you should insert all words read from the user. You can implement more than one Trie data structure. Finally, you should complete following functions:
Void Search (String arg): This function should print true if given argument is in your Trie, otherwise it should print false.
Void countPrefix(): This function takes all the strings in Trie and checks if a string is a prefix of other strings in Trie. It prints the number of occurrences for each string. For this function, you may use a symbol table that keeps track of the number of appearances of each key. Also, you should print prefix in alphabetical order of corresponding string.
Note: You can change the parameter for this method if you need!
Void reverseFind (String suffix): This function should print all strings end with given suffix in your Trie, lexicographically. For this function, you may consider using multi-trie solution, or research and use more complex data structures such as suffix arrays. Also, you should print string in alphabetical order.
Void ShortestUniquePrefix (Trie trie): This function should print shortest unique prefix to identify each string in your trie. If there is not any unique prefix, print not exists .
Note: You can change the parameter for this method if you need!
Void LongestCommonPrefix (): This function should print longest common prefix for all strings in your trie. If there is not any unique prefix, print not exists .
Note: You can change the parameter for this method if you need!
Sample Input 1:
7 // number of inputs
at // word 1
atomy //word 2
ate
ato
borned
born
curve // word 7
Enter Operation Code:
//1- Search, 2- countPrefix,
//3- reverseFind, 4- ShortestUniquePrefix
// 5- LongestCommonPrefix, 6- exit
1 //call Search Function
ate
True
Enter Operation Code:
1
Atel
False
Enter Operation Code:
2 //call countPrefix
at: 3
ate: 0
ato: 0
atomy: 0
born: 1
borned: 0
curve: 0
Enter Operation Code:
3 // call reverseFind
e
ate
curve
Enter Operation Code:
3
ned
borned
Enter Operation Code:
4 // call ShortestUniquePrefix
at: not exists
ate: ate
ato: ato
borned: borne
born: not exists
curve: c
Enter Operation Code:
5 // call LongestCommonPrefix
not exists
Enter Operation Code:
6
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access with AI-Powered Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started