UVa 10887

From Algorithmist
Jump to navigation Jump to search

10887 - Concatenation of Languages[edit]

Summary[edit]

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?

Explanation[edit]

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.

Gotcha's[edit]

  • 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.

Input[edit]

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

Output[edit]

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

External Links[edit]

  • Discussion at online-judge.uva.es/board (post any questions here)