Game with String
Contest: Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)
Difficulty rating: 1600
Tags: implementation, probabilities, strings

Vasya and Kolya play a game with a string, using the following rules. Initially, Kolya creates a string s, consisting of small English letters, and uniformly at random chooses an integer k from a segment [0, len(s) - 1]. He tells Vasya this string s, and then shifts it k letters to the left, i. e. creates a new string t = sk + 1sk + 2... sns1s2... sk. Vasya does not know the integer k nor the string t, but he wants to guess the integer k. To do this, he asks Kolya to tell him the first letter of the new string, and then, after he sees it, open one more letter on some position, which Vasya can choose.

Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability.

Note that Vasya wants to know the value of k uniquely, it means, that if there are at least two cyclic shifts of s that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win.

Input format:
The only string contains the string s of length l (3 ≤ l ≤ 5000), consisting of small English letters only.

Output format:
Print the only number — the answer for the problem. You answer is considered correct, if its absolute or relative error does not exceed 10 - 6.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $${ \frac { | a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.

In the second example if the first opened letter of t is "t" or "c", then Vasya can't guess the shift by opening only one other letter. On the other hand, if the first letter is "i" or "a", then he can open the fourth letter and determine the shift uniquely.

Example input:
technocup

Example output:
1.000000000000000

Example input:
tictictactac

Example output:
0.333333333333333

Editorial:
Idea. Let's consider all possible c1 that will be first in t. Then, let's consider all possible numbers of second letter that Vasya will ask about — this will be d. If pair of letters (c1, c2) occurs only once at d distance, than if c2 opens second time, Vasya will be able to determine shift.
Solution. Let's loop through all letters at d distance from all c1 letters and for each symbol c2 we will calculate number of such letters. This can be done in O(cnt(c1)), where cnt(c1) is number of letters c1 in initial string. Now, if we fix such d after opening c1, that maximizes number of unique pairs(we will name it p) (c1, c2) at d distance, this will be optimal d, and conditional probability of victory in situation of fixed c1 equals p / cnt(c1).
Now we only need to sum up conditional probabilities for different c1. Probability of c1 equals cnt(c1) / n, thus answer is $$\sum \frac{p}{cnt(c_1)} \cdot \frac{cnt(c_1)}{n} = \sum \frac{p}{n}$$.