# UVa 10887

Jump to navigation
Jump to search

## Contents

## 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)