Aho-Corasick-algorithm

Assume that we have a poem whose length is $100^{100}$. Try to find how beautiful is this poem. There are some good words(S_i), with some weights assigned to each of them (C_i). The formula for calculating the beauty of this poem string (T) is :

$$ \sum_{i=1}^{n} \frac{C_i \times \text{occurs}(T, S_i)}{|T|} $$

Input: In the first line you have n, which shows the number of beautiful words. Then, in the next line, you'll have C_i s. In the n following lines, you'll get n beautiful words.

Sample Input	Output
1 10 aa	10.000000
4 2 3 4 5 abb bba aab baa	3.500000

Note: Only around 16% of students could solve this problem 100% correctly for all of the test cases