manacher

vector<int> construct_d1 (string const & s,int n) {
	vector<int> d1(n);
	for (int i = 0,l = 0,r = -1; i < n; ++i) {
		int k = (i > r) ? 1 : min(d1[l + r - i],r - i + 1);
		while (0 <= i - k and i + k < n and s[i - k] == s[i + k]) {
			++k;
		}
		d1[i] = k--;
		if (i + k > r) {
			l = i - k,r = i + k;
		}
	}
	return d1;
}

vector<int> construct_d2 (string const & s,int n) {
	vector<int> d2(n);
	for (int i = 0,l = 0,r = -1; i < n; ++i) {
		int k = (i > r) ? 0 : min(d2[l + r - i + 1],r - i + 1);
		while (0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]) {
			++k;
		}
		d2[i] = k--;
		if (i + k > r) {
			l = i - k - 1;
			r = i + k;
		}
	}
	return d2;
}