Update appNew update is available. Click here to update.

Longest Common Prefix

Last Updated: 15 Feb, 2019
Difficulty: Moderate


Try Problem

Vidit is frequently among the "Wrong-doers" list. To curb his menace, Ms. Manisha, his algorithms teacher, gave him an assignment to keep him busy.

Ms. Manisha coins a term "longest common prefix", which is defined as longest word with which both words start with. For example: the longest common prefix of words: "notify" and "notification" is the word "notif".

Now, Ms. Manisha gives a database of N words to Vidit. Ms. Manisha also gives an algorithm to search a word X in the database. The algorithm is simple and is written as:

1. Compare the word X with each word in the database. We keep on comparing till we find a mismatching letter or end of one of the words is reached.

2. After that it is established either words are equal/unequal or that one is longer than the other.

3. When the algorithm finds the word X in the database, it terminates.

Analysing the algorithm, it shows that the number of steps needed to find a word W is equal to the sum of the lengths of the longest common prefixes of X and each of the words it was compared to.

Vidit comes to you and asks you to write a program that calculates the number of steps the algorithm uses to find each of the Q query words.

Input Format:
 The first line contains an integer N (1 ≤ N ≤ 30000), the number of words in the database.
 Each of the following N lines contains a single word from the database. The words are given in the order the algorithm compares them to a query word. All words in the database will be distinct.
 The following line contains an integer Q (1 ≤ Q ≤ 30000), the number of words searched for.
 Each of the following Q lines contains a single query word.
 All words in the input will be strings of less than 30 lowercase letters of the English alphabet.
 Time Limit: 2 seconds
Output Format:
 Output one integer per line for each query word, the number of steps the algorithm uses when searching for the word.