You are not logged in. Please login at www.codechef.com to post your questions!

×

Longest Common Prefix (help)

Please help me to solve this 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.

Constraints: 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.

Sample Test Cases:

Sample Input 1:

8

majmunica

majmun

majka

malina

malinska

malo

maleni

malesnica

3

krampus

malnar

majmun

Sample Output 1:

8

29

14

Explanation: In the first test case, the number of steps to search for the word "krampus" is 8 because the algorithm only needs to compare its first letter to each word in the database.

When searching for the word "malnar", we need three steps for each of the first three words, and four steps for each of the remaining five words, for a total of 29 steps.

To find the word "majmun" we use a total of 14 steps. For the first word in the database, we have six successful comparisons and one step in which we determine that the word "majmunica" is longer than the query word. For the second word, we also have six successful comparisons and a final step in which it is established that the words are equal. After finding the word, the algorithm terminates with great joy

This question is marked "community wiki".

asked 16 Feb, 20:09

ashudeshwal's gravatar image

3★ashudeshwal
302
accept rate: 0%

edited 16 Feb, 20:10

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,736

question asked: 16 Feb, 20:09

question was seen: 30 times

last updated: 16 Feb, 20:10