$*$Please solve it with Java language!$*$In this homework, you must implement your own graph data structure by taking inspiration from your textbook and use it to help to solve problem. You are not allowed to use any external library or $.$jar file. Any solutions without using trie data structure are not evaluated! In this homework, 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: $(10$ points$)$ Void Search $($String arg$)$: This function should print true if given argument is in your Trie, otherwise it should print false. $(20$ points$)$ 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! $(20$ points$)$ 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. $(25$ points$)$ 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! $(25$ points$)$ 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$ Sample input $2$: $3//$ number of inputs

at $//$ word $1$

atomy $//$word $2$

ate $//$word $3$

ato $//$word $4$

Enter Operation Code:

$//1-$ Search, $2-$ countPrefix,

$//3-$ reverseFind, $4-$ ShortestUniquePrefix

$//5-$ LongestCommonPrefix, $6-$ exit

$5//$call LongestCommonPrefix

at

Enter Operation Code:

$6$