All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Hey! Please help Pradyumn!
Tag(s):

BFS, DFS, Hashing, Medium, Trie

Problem
Editorial
Analytics

Pradyumn is tired of using auto - correct feature in his smartphone. He needs to correct his auto - correct more times than the auto - correct corrects him. Pradyumn is thinking to make his own app for mobile which will restrict auto - correct feature, instead it will provide auto - completion. Whenever Pradyumn types factorial, auto - correct changes it to fact. Pradyumn's App will show options such as fact, factorial, factory. Now, he can chose from any of these options. As Pradyumn is busy with his front - end work of his App. He asks you to help him. He said "You will be given set of words(say a dictionary of words in uppercase and lowercase letters both, words may repeat too). Now, as user starts the app, he will make queries(in lowercase letters only). So, you have to print all the words of dictionary which have the prefix same as given by user as input(in lowercase only). And if no such words are available, add this word to your dictionary." As you know, Pradyumn want this app to be as smart as him :P So, implement a program for him such that he can release it on Fun Store.

INPUT CONSTRAINTS
\(1 \le N \le 30000\)
\( sum(len(string_i)) \le 2 * 10^5 \)
\(1 \le Q \le 10^3 \)
\(1 \le len(querystring_i) \le maxLength(All Words Length)\)

INPUT FORMAT
Single integer N which denotes the size of words which are input as dictionary
N lines of input, where each line is a string of consisting lowercase/uppercase letter
Single integer Q which denotes the number of queries.
Q number of lines describing the query string on each line given by user

OUTPUT FORMAT

If auto - completions exists, output all of them in lexicographical order(lowercase) else output "No suggestions" without quotes

NOTE Auto - completion feature never consider the lowercase/uppercase for suggestions. Query strings are lowercase. Dictionary of words contains both types of cases(Uppercase & Lowercase). Multiple occurrences of word is possible.

SAMPLE INPUT
3
fact
factorial
factory
2
fact
pradyumn
SAMPLE OUTPUT
fact
factorial
factory
No suggestions
Explanation

Already explained above.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

The LNM Institute of Information Technology

Challenge Name

LNMIIT Algorithms Cup - June 2017

Notifications
View All Notifications

?