|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
D - Diccionário Portuñol
Languages: C, C++, Java, Haskell, Python, Pascal, JavaScript, Tiger, C#
Time & Memory limits: (details)
Portuñol is a special language that was naturally developed in Latin America. Since almost half of Latin America speaks Portuguese (Português) and almost half speaks Spanish (Español), the mixing of both languages is natural.
Each word in Portuñol is made by taking a non-empty prefix of a Portuguese word and a non-empty suffix of a Spanish word, and concatenating them together. A prefix of a word is any word that can be obtained by erasing zero or more characters from its right end. A suffix of a word is any word that can be obtained by erasing zero or more characters from its left end. The name of the language itself comes from taking a prefix of the word “Português” (Portu) and a suffix of the word “Español” (ñol), and concatenating them.
Of course, not every possible way of combining two words will result in something meaningful, or even pronounceable, but that is not important. We want you to write a program to count the number of different Portuñol words.
You will be given two non-empty sets of words to test your program. The first set will represent Portuguese words and the second set will represent Spanish words. You need to calculate the number of different Portuñol words that can be made using the prefix and suffix rule described above. Note that the same word may be constructed in several ways, but it still needs to be counted as one. Also note that the input sets are just to test your program, so they do not need to be made out of actual Portuguese or Spanish words.
Input
Each test case is described using several lines. The first line contains two integers $P$ and $S$ representing respectively the number of Portuguese words and the number of Spanish words $(1 \leq P, S \leq 1000)$. Each of the next $P$ lines contains a Portuguese word, and after that each of the next $S$ lines contains a Spanish word. Each word is a non-empty string of at most $1000$ characters; each character is one of the $26$ standard lowercase letters (from $\texttt{‘a’}$ to $\texttt{‘z’}$). You may assume that within each test case no two Portuguese words are the same, and that the sum of the lengths of all the Portuguese words is at most $10^5$. The same holds for the Spanish words.
The last test case is followed by a line containing two zeros.
Output
For each test case output a line with an integer representing the number of different words that can be constructed by concatenating a non-empty prefix of a word in the first set (Portuguese words) and a non-empty suffix of a word in the second set (Spanish words).
Sample test(s)
Input
3 3
mais
grande
mundo
mas
grande
mundo
1 5
a
aaaaa
aaaaaa
aaaaaaa
a
aaaaaaaaa
1 1
abc
abc
0 0
Output
182
9
8