930B - Game with String - CodeForces Solution

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define dec double 
#define ll long long
using namespace std;
const int MAXN = 5005;

int n; char s[MAXN][MAXN];

// 第一个位置是什么、第几位、有几个 
int cnt[26][MAXN][26], num[26]; dec ans;

int main() {
	scanf("%s", s[0] + 1); n = strlen(s[0] + 1);
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			s[i][j] = s[i - 1][j + 1];
		}
		s[i][n] = s[i - 1][1];
	}
	
	for (int i = 0; i < n; i++) {
		num[s[i][1] - 'a'] ++;
		for (int j = 2; j <= n; j++) {
			cnt[s[i][1] - 'a'][j][s[i][j] - 'a'] ++;
		}
	}
	for (int i = 0, mx, tmp; i < 26; i++) {
		if (!num[i]) continue;
		mx = 0;
		for (int j = 2; j <= n; j++) {
			tmp = 0;
			for (int k = 0; k < 26; k++) {
				if (cnt[i][j][k] == 1) tmp ++;
			}
			mx = max(mx, tmp);
		}
		ans += (dec)mx / n;
	}
	printf("%.15lf", ans);
	return 0;
}