CF930B Game with String

Vasya 和 Kolya 玩一个与字符串相关的游戏，规则如下：最开始，Kolya 创建一个只包含小写英文字母的字符串 $s$，并从区间 $[0, \text{len}(s)-1]$ 中等概率随机选择一个整数 $k$。他将字符串 $s$ 告诉 Vasya，然后将 $s$ 向左循环移动 $k$ 位，得到新字符串 $t = s_{k+1}s_{k+2}\ldots s_{n}s_{1}s_{2}\ldots s_{k}$。Vasya 并不知道整数 $k$ 以及字符串 $t$，但他想猜出整数 $k$。为此，他可以让 Kolya 告诉他新字符串的第一个字母，然后在看到这个字母后，再选择一个位置，让 Kolya 告诉他该位置上的字母。 Vasya 明白，他无法保证一定获胜，但他想知道如果他采取最优策略，获胜的概率是多少。请你计算这个概率。 注意，Vasya 需要唯一确定 $k$ 的值，也就是说，如果有至少两个 $s$ 的循环移位与 Vasya 已知的信息相符，则 Vasya 输了。当然，在游戏的每一步，Vasya 都会选择使自己获胜概率最大的策略。

输入仅一行，包含字符串 $s$，长度为 $l$，$3 \leq l \leq 5000$，只包含小写英文字母。

输出一个实数，表示 Vasya 获胜的概率。你的答案被认为是正确的，当且仅当其绝对误差或相对误差不超过 $10^{-6}$。

在第一个样例中，Vasya 总是可以在看到第一个字母后再打开第二个字母，这样循环移位总能被唯一确定。 在第二个样例中，如果 $t$ 的第一个字母是 "t" 或 "c"，Vasya 无法仅通过再打开一个字母来猜出移位量。但如果第一个字母是 "i" 或 "a"，他可以打开第四个字母，从而唯一确定移位量。 由 ChatGPT 4.1 翻译