All submissions for this problem are available.
After Playing Game in Alkhwarizm, BKUL is now working as a software devlopper. Recently he has devlopped a small search engine which perform search for a string S in database. He has used following Algorithm for searching.
Suppose there are N strings in database. It starts comparing string with each string in the database from the beginning. Two strings are compared letter by letter from start until a mismatch found or end of one of the string reaches.When algorithm find the string S in database, it terminates. Every comparison is counted as a single step.
Your task is to write a program that calculates number of steps the algorithm uses to find each of the Q query strings.
Input will begin with an integer N, number of strings in data base. Each of the following N lines contain a single string from database. Strings are given in the order the algorithm compare them to a query string. All strings in database will be distinct.
The following line contains an integer Q, the number of queries. Each of the following Q lines contain a single query string. All strings in the input will be strings of less than 30 lowercase letters of the English alphabet.
Print one integer per line for each query string, the number of steps algorithm uses while searching for the string in the same order as given in the input.
1 <= N <= 30,000
1 <= Q <= 30,000
Input: 5 avsvinaystp bvksgptk vkrjgr robot habbit 3 habbit vkrjgr bvkija Output: 11 9 8
Output for first query is 11, which is result of 1 + 1 + 1 + 1 + 7, for corresponding strings in database.
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.