| Submit | All submissions | Best solutions | Back to list |
TRYCOMP - Try to complete |
You are given hundreds of thousands of words from a book.
For each query you are given a string S. Find the most occurring word in the book with S as prefix.
Input
The first line consists of an integer n, the number of words in the text book. The next n lines consists of the words in the book. The next line consists of an integer q, the number of queries. Next q lines consists a string S.
Output
For each query String S, print the most occurring word in the book with S as prefix along with the number of occurrences of that word. If there are many such words, print the lexicographically smallest word. If there is no such word, print -1.
Constraints
1 <= n <= 5*10^5
1 <= q <= 10^5
1 <= word length <= 10
All the characters in the word are lowercase letters of the English alphabet.
Sample
Input 10 apple banana orange applet banana oriental orange oriental applet bangalore 8 ban bang app or oriental apple hobbits oranges Output banana 2 bangalore 1 applet 2 orange 2 oriental 2 applet 2 -1 -1
Problem source: Inspired from autocomplete feature on Google keyboard.
| Added by: | cegprakash |
| Date: | 2016-10-22 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: MAWK BC BF NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2017-07-05 17:51:58
getting timed out ! |
|
|
2016-11-27 17:52:49 cegprakash
no |
|
|
2016-11-27 17:17:18
Are there blank lines in between 2 words or 2 queries? (in the input) |
|
|
2016-11-27 12:55:17 cegprakash
Because there is only one apple. You print the lexicographically smallest only in case of ties. |
|
|
2016-11-27 10:58:22
then for query apple....apple should come first,but applet is the output....can u explain it how??? |
|
|
2016-11-27 10:09:49 cegprakash
It is "ban". If you compare "ban" < "bangalore" it'll return true. Therefore ban is lexicographically smaller. Moreover, in a dictionary with those two words, ban would appear earlier. Last edit: 2016-11-27 10:11:45 |
|
|
2016-11-27 08:53:39
What is the expected output for - 4 ban ban bangalore bangalore 1 ban |
RSS