P| Diccionário Portuñol |
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 nonn 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.
P,
S1000).
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 `a' to `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 105 . The same holds for the Spanish words.
The last test case is followed by a line containing two zeros.
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).
3 3 mais grande mundo mas grande mundo 1 5 a aaaaa aaaaaa aaaaaaa a aaaaaaaaa 1 1 abc abc 0 0
182 9 8