Codeforces 204C. Little Elephant and Furik and Rubik

問題

英大文字からなる長さの等しい文字列a, bが与えられる。
a, bから長さの等しい、空でない連続する部分文字列x, yを取る。

x, yはその全ての候補の中から一つが等しい確率で選ばれる。
f(x, y)を、xi = yi（xのi番目の文字とyのi番目の文字が等しい）なるiの個数とする。
f(x, y)の期待値を求めよ。

制約条件

a, bの長さ≦2 * 10^6

方針

AからZの文字それぞれに対して一致する回数を数え上げる。
これは愚直にやるとO(n^2)かかるが、上手くやるとO(n)で数えられる。

Aの一致回数を数えたいとき、
a XXXAXXXXXXX
b XXXXXAXXXXX

となっていたら、aで、Aを最後に持つ部分文字列は4つ。
bのAに対して、この4つは対応するものがある。

これをどこまで右に伸ばせるかは、bのAの右からの文字数を見ればいい。
それぞれが右に6つまで伸ばせるので、
4 * 6で24通りの一致がある。

つまり、
a XXXXAXXXXX
b XXXXXXXAXX
のように、aのAよりも後ろにあるAについて、一致回数は
Σ(aのAの位置 * bのAの右からの位置)という風に求められるので、
bのAの右からの位置の和を持っておけば全体でO(n)で求められる。

同様にして、
a XXXXXXXAXX
b XXXAXXXXXX
のように、左側にあるAの一致回数については、
aの右側からの位置 * bのAの左からの位置という風に求められる。

あとは一致回数を部分文字列の組み合わせの個数で割ればよい。

ソースコード

int n;
string a, b;

double calc(char c){
	double res = 0, left = 0, right = 0;
	
	rep(i, n) if(b[i] == c) right += n - i;
	rep(i, n){
		if(a[i] == c){
			res += right * (i + 1);
			res += left * (n - i);
		}
		if(b[i] == c){
			right -= n - i;
			left += i + 1;
		}
	}
	return res;
}

void run()
{
	cin >> n;
	cin >> a >> b;
	double ans = 0, sum = 0;
	for(char i = 'A'; i <= 'Z'; i++) ans += calc(i);
	rep(i, n) sum += (i + 1.0) * (i + 1.0);
	
	printf("%.9f\n", ans / sum);
}