【2022牛客多校】第五场 Crazy Thursday 二分+字符串哈希

https://ac.nowcoder.com/acm/contest/33190/G

题意
给你一个长为n的字符串s，求s中分别以'k'、'f'、'c'结尾的回文串数量

\(n <= 5e5\)

思路
首先暴力枚举区间端点加判断，为 \(O(n^3)\) ，肯定会超时

注意到对于每个位置的字符，可以找到以它为中心的回文串的最大长度，那么（仍以这个字符为中心的）最大串内部的串也都是回文串

那么考虑二分以每个字符为中心的串的回文最大半径，找到最大回文半径后可以利用区间加算出答案

此外还需注意回文串可能以某个字符为中心，长度为奇数；也可能以某两个相同的字符为中心，长度为偶数。这里需要分情况讨论

还有一个问题，二分的check如果是 \(O(n)\) 的，仍然会超时（亲身实践

那么需要用到更快的 \(O(1)\) 的check方式——字符串哈希

细节见代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 5e5+10, seed = 31;
int t, n, m;
char s[N];
int prek[N], pref[N], prec[N];
ll ansk, ansf, ansc;
ull h[N], rh[N], base[N];

inline ull Hash(int l, int r) {
	return h[r] - h[l - 1] * base[r - l + 1];
}

inline ull rHash(int l, int r) {
	return rh[l] - rh[r + 1] * base[r - l + 1];
}

inline bool check(int x, int r) {
	return Hash(x - r + 1, x) == rHash(x, x + r - 1);
}

inline bool check2(int x, int r) {
	return Hash(x - r + 1, x) == rHash(x + 1, x + r);
}

void init() {
	base[0] = 1;
	for (int i = 1; i <= n; i++) base[i] = base[i - 1] * seed;
	h[0] = 0;
	for (int i = 1; i <= n; i++) {
		h[i] = h[i - 1] * seed + s[i] - 'a';
	}
	rh[n + 1] = 0;
	for (int i = n; i >= 1; i--) {
		rh[i] = rh[i + 1] * seed + s[i] - 'a';
	}
}

void solve() {
	//ji
	for (int i = 1; i <= n; i++) {
		int l = 1, r = min(i, n - i + 1), mid, ans;
		while (l <= r){
			mid = (l + r) >> 1;
			if (check(i, mid)) {
				l = mid + 1;
				ans = mid;
			}
			else r = mid - 1;
		}
		ansk += prek[ans + i - 1] - prek[i - 1];
		ansf += pref[ans + i - 1] - pref[i - 1];
		ansc += prec[ans + i - 1] - prec[i - 1];
	}
	//ou
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i + 1]) continue;
		int l = 1, r = min(i, n - i), mid, ans = -1;
		while (l <= r){
			mid = (l + r) >> 1;
			if (check2(i, mid)) {
				l = mid + 1;
				ans = mid;
			}
			else r = mid - 1;
		}
		if(ans == -1) continue;
		ansk += prek[ans + i] - prek[i];
		ansf += pref[ans + i] - pref[i];
		ansc += prec[ans + i] - prec[i];
	}
}

int main(){
    cin >> n;
	scanf("%s", s + 1);
	init();
	for (int i = 1; i <= n; i++) {
		prek[i] = prek[i-1] + (s[i] == 'k');
		pref[i] = pref[i-1] + (s[i] == 'f');
		prec[i] = prec[i-1] + (s[i] == 'c');
	}
	solve();
	printf("%lld %lld %lld\n", ansk, ansf, ansc);
    system("pause");
    return 0;
}