Word Search
InterviewTime limit1sMemory limit128 MB
Given N database words compared in order against a query using character-by-character matching that also checks for word-end, compute total comparisons per query.
- Level
Medium5 of 10
- Topics
- Trie, String, Simulation
- Solved
- No attempts yet
Problem
A database stores N words.
The search algorithm compares a query word W with the database words one by one, in the order they were given. When comparing two words, it starts from the first character and continues until it sees different characters or confirms that one of the words has ended. If it finds a word equal to W, the search stops immediately.
Assume that the length of a word is not known before the comparison. Therefore, even if every real character matched, the algorithm must compare the next position once more to determine whether the word has ended. For example, when comparing abc and abcd, the algorithm discovers that the words are different at the fourth position, where one word has already ended. When comparing abc and abc, it also needs the fourth comparison to confirm that both words ended there.
If the query word is not in the database, the search ends after comparing it with every database word. Given the database words and the query words, compute how many character comparisons are needed for each query.
Input
The first line contains the number of database words N. (1 <= N <= 30000)
Each of the next N lines contains one database word. Searches must use exactly this input order, and all database words are distinct.
The next line contains the number of query words Q. (1 <= Q <= 30000)
Each of the next Q lines contains one query word.
Every database word and query word consists only of lowercase English letters, and each length is less than 30.
Output
For each query word, print the number of character comparisons needed until that search finishes, one result per line.