10887 - Concatenation of Languages
Two sets of strings are given. What is the number of distinct strings in the set, formed by concatenating every word from the first set with every word from the second one?
The simplest solution is just to generate and count the words in the resultant set. In order to do it quickly, you need an efficient data structure to keep the generated words. Binary search trees and STL's data structures are too slow to run in time, but a hand-coded implementation of hashtable should be enough.
- One (or both) of the sets may be empty (in this case the answer is 0.)
- Some of the words may be empty strings. Be careful with input parsing code.
10 3 2 cat dog mouse rat bat 1 1 abc cab 3 3 a b a b 2 2 a aa a aa 3 3 a ab abc bcd cd d 5 7 a ab abc abcd abcde bcde cde de e defg dzxy 5 5 a aa aab abc ad a ab b bc cd 0 0 1 1 a b 4 0 alpha beta gamma delta
Case 1: 6 Case 2: 1 Case 3: 7 Case 4: 3 Case 5: 7 Case 6: 31 Case 7: 24 Case 8: 0 Case 9: 1 Case 10: 0
- Discussion at online-judge.uva.es/board (post any questions here)