P7937 [COCI 2007/2008 #5] BAZA

Define the common prefix of two strings as the substring that both strings share starting from the beginning. For example, the common prefix of the string `identity` and the string `idealistic` is `ide`. A database contains $N$ strings. The algorithm used to search for a string $W$ in this database is very primitive: it compares $W$ with the strings in the database one by one. For each pair of strings, it compares characters one by one until it finds a mismatching character or reaches the end of one of the strings, and then performs one final comparison to determine whether the two strings have the same length. When $W$ is found in the database, the algorithm stops. By analyzing this algorithm, we find that the number of steps needed to find $W$ in the database equals the number of strings compared with $W$, plus the sum of the lengths of the common prefixes between $W$ and all strings that were compared with it. There are $Q$ query strings. Write a program that computes, for each query string, how many steps the program needs to find this word in the database. **Please note the unusual memory limit for this problem.**

The first line contains an integer $N$, the number of strings in the database. The next $N$ lines each contain one string from the database. These strings are given in the order in which the algorithm checks them, and they are all distinct. The next line contains an integer $Q$, the number of query strings. The next $Q$ lines each contain one query string.

For each query string, output one line with one integer, the number of steps required for the program to find this word in the database.

For $100\%$ of the data, $1 \le N, Q \le 3 \times 10^4$, all strings have length $< 30$, and they contain only lowercase letters. ### Explanation for Sample 2: For Sample 2, the number of steps used to search for the string `krampus` is $8$, because we only need to compare the first character of each string in the database with this string. When searching for `malnar`, each of the first three strings requires $3$ comparisons, and each of the remaining five strings requires $4$ comparisons, so there are $29$ comparisons in total. To find the string `majmun`, we perform $14$ comparisons in total. For the first word, we make $6$ successful comparisons, but the last comparison determines that the string `majmunica` is longer than `majmun`. For the second string, we also make $6$ successful comparisons, and in the final comparison we find that the two strings have equal length, so the algorithm stops. The score for this problem follows the original contest setting, with a full score of $90$ points. Translated by ChatGPT 5