Game with String

题意翻译

Vasya和Kolya根据以下规则用一个字符串玩游戏。Kolya创建一个由小写英文字母构成的字符串 s ，并在 [0,len(s) - 1] 范围内任选一个整数 k 。他把这个字符串的内容告诉Kolya，然后把从左数起的 k 个字母放到右边去。换句话说，创建一个新的字符串 t = sk+1 sk+2...sn s1 s2...sk-1 sk。Vasya既不知道 k 的大小又不知道字符串 t 的具体内容，但他想猜一猜 k 是多少。为了猜对，他请求Kolya告诉他新字符串的首字母，然后再告诉他任意一个位置的字母，而这个字母的位置由Vasya自己决定。 Vasya明白他不能保证自己一定能猜对，但他想要知道如果他以最优解法进行求解，那么他获胜的概率有多大。 请注意，Vasya想保证通过他所得到的信息来得到唯一的 k 值，换句话说，如果有至少两个符合Vasya已知信息的字符串 t ，那么Vasya就输了(例：Vasya知道第1个字母是 a ，第2个字母是 b ，那么如果在更改后的字符串中至少有两个字符串首字母都为 a ，次字母都为 b ，那么Vasya就输了，因为符合他所知信息的，更改后的字符串至少有两个，其对应的 k 值也至少有两个。不考虑在多个可能的 k 值取值中蒙对的概率。)。 输入格式： 输入长度为 l 的字符串 s (3 <= l <= 5000)。s 中仅包含小写英文字母。 输出格式： 输出一个数表示获胜概率。如果你的答案与标准答案相差小于10^(-6)就判定你的答案是正确的。 说明： 在样例一中无论 k 是多少，Vasya总可以在得知首字母和第2个字母的情况下猜对 k 值，并且 k 值的取值总是唯一的。 在样例二中，如果更改后的字符串首字母为"t"或者"c"，那么Vasya并不能通过得知其他位置的任意一个字母来得到 k 的唯一取值。换句话说，如果更改后的字符串首字母为"i"或者"a"，那么他就可以通过得知第四个位置的字母来得到 k 的唯一取值。 Translated by @radish布団

题目描述

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=s_{k+1}s_{k+2}...\ s_{n}s_{1}s_{2}...\ s_{k} $ . 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.

输入输出格式

输入格式

The only string contains the string $ s $ of length $ l $ $ (3<=l<=5000) $ , consisting of small English letters only.

输出格式

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 

输入输出样例

输入样例 #1

technocup

输出样例 #1

1.000000000000000

输入样例 #2

tictictactac

输出样例 #2

0.333333333333333

输入样例 #3

bbaabaabbb

输出样例 #3

0.100000000000000

说明

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.