Submit: 0 Solved: 0

[Submit] [Status] [Web Board] [Creator:]

Please solve the following problem:

Given a string s, suppose another string r is chosen randomly from all different substrings of s with equal probability, what is the expected number of occurrence of r in s?

For example, if s =“aab”, there are 5 substrings namely “a”, “b”, “aa”, “ab”, “aab”, thus the answer is (2 + 1 + 1 + 1 + 1)/5 = 6/5.

There are several test cases.

For each test case, there is a single line containing a string of Latin letters whose whose length will never exceed 200.

Input is terminated by EOF.

For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is a real number representing the answer.

A result within absolute error of 10

`aab`

`Case 1: 1.20000`