Algorithm
Problem Name: URI Online Judge | 2635
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2635
Web Browser
By Guilherme de Lima Bernardes, UNB 
Brazil
Timelimit: 1
Lucas is a pretty radical guy when it comes to software licenses. Since beginning his undergraduate degree in computer engineering, he seeks to develop all the tools he needs. All this started after bad experiences using proprietary software. Now he believes that a real programmer must be self-sufficient, that is, he must build all the programs he needs, from a simple calculator to his own operating system.
This semester, Lucas is studying the web systems development course. To continue his philosophy of life, using only software he built himself, Lucas is already programming his own web browser. Much of the work has been completed, but some functionality still needs to be finished.
Lucas' browser has a search field where the user can enter a keyword, and clicking a confirmation button it will redirect to another page with the results of his search. When some string is entered in the search field, Lucas wants his program to display, below, some options to auto complete this string according to the searches already performed by the user.
For example, if the words "algoritmos" and "algas" have already been searched, when typing the string "alg", the program should suggest the words "algorithms" and "algas". Therefore, for each string entered, the program should suggest previously searched words prefixed with this string. If any word is equal to the typed string, it should also be suggested.
Lucas is concerned about the amount of words his program can suggest, and the maximum size they can reach. So he asked you to help him by writing a program where given a few words already searched and a series of queries composed of a string, indicate how many words the browser should suggest to the user, and the length of the largest of these words.
Input
The input is composed of several test cases. The first line of a test case has an integer N (1 ≤ N ≤ 10^4) indicating the number of words that have already been searched by the Lucas’ program. Each of the next N lines contains a nonempty string of a maximum of 100 lowercase letters [a - z]. For each test case, N words are different. Then there will be an integer Q (1 ≤ Q ≤ 100) indicating the number of queries. Each of the next Q lines describes a query with a non-empty string of a maximum of 100 lowercase letters [a - z], representing a string entered in the search field.
Output
For each test case print Q lines, where the i-th row is the answer to the i-th query. The response of each query should be composed of two integers separated by space, representing, respectively, the number of words suggested by the program when entering the string indicated by the ith query, and the length of the largest word contained in that subset. If no words are suggested, print -1.
| Input Sample | Output Sample |
|
5 maratonaicpc maraton programacao progress inputs 3 marat programacao outputs |
2 12 1 11 -1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
int n, q, wc, l;
string s;
while (cin >> n)
{
wc=-1;
l=0;
vector < string>v, in, a;
while (n--)
{
cin >> s;
v.push_back(s);
}
cin >> q;
while (q--)
{
cin >> s;
}
cout << wc << endl;
break;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
var prompt = function(texto) { return lines.shift();};
const searchedSize = parseInt(prompt("answers"));
var searched = [];
for (let i = 0; i < searchedSize; i++) {
searched.push(prompt());
}
const querySize = parseInt(prompt("queries"));
for (let i = 0; i < querySize; i++) {
let query = prompt();
let suggestions = 0;
let suggestionSize = 0;
for (let word of searched) {
if (query == word.substring(0, query.length)) {
suggestions++;
suggestionSize = Math.max(suggestionSize, word.length);
}
}
if (suggestions == 0) {
console.log(-1);
} else {
console.log(suggestions + " " + suggestionSize);
}
}
Input
Output