RandomConcat | Topcoder Archive

Problem Statement

You have several (at most 15) strings in the String[] pieces. You are going to construct a single string called the haystack by shuffling the pieces into a random order and concatenating them. (Each permutation of pieces is equally likely.)

You also have a String needle. Compute and return the expected number of occurrences of the needle in the haystack.

Definition

Class:: RandomConcat
Method:: expectation
Parameters:: String[], String
Returns:: double
Method signature:: double expectation(String[] pieces, String needle)
(be sure your method is public)

Notes

Your return value must have an absolute or a relative error at most 1e-9.

Constraints

pieces will have between 1 and 15 elements, inclusive.
Each element of pieces will have between 1 and 50 characters, inclusive.
needle will have between 1 and 50 characters, inclusive.
Each character in each of the strings will be a lowercase English letter ('a'-'z').

Examples

```
{"hahaha"}
```
```
"aha"
```
```
Returns: 2.0
```
Haystack will always be "hahaha". This string contains two occurrences of the string "aha". Note that the two occurrences overlap partially.
```
{"hah","ah"}
```
```
"aha"
```
```
Returns: 0.5
```
With probability 1/2 haystack will be "hahah" and there is one occurrence of the substring "aha". With probability 1/2 haystack will be "ahhah" and there are no occurrences of "aha". Hence, the expected number of occurrences is 0.5.
```
{"t","o","p","c","o","d","e","r"}
```
```
"topcoder"
```
```
Returns: 4.9603174603174596E-5
```
Two of the 8! permutations produce the haystack "topcoder" that exactly matches the given needle.
```
{"hellotopc","oderhellotop","coderbye"}
```
```
"topcoder"
```
```
Returns: 0.6666666666666666
```
If we concatenate the pieces in the given order, there will be two occurrences of "topcoder". Two other concatenation orders will produce a haystack with one occurrence of the needle, and the remaining three produce a haystack that contains no needles at all.

{"aabaa","aabaaaaa","aba","goodluck","havefun"}

"aaaa"

Returns: 2.8000000000000016

```
{"a","a","aa","b"}
```
```
"aba"
```
```
Returns: 0.5
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.