可爱萌新求助简单哈希 37pts
查看原帖
可爱萌新求助简单哈希 37pts
852144
Loser_Syx楼主2024/7/18 12:01
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <random>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch = '\n') {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
struct node {int l, r, v;};
const int N = 66666, base = 31, mod = 1e9 + 7;
int hsh[N], hsh2[N], pw[N];
int gethash(int l, int r) { return ((hsh[r] - hsh[l-1] * pw[r - l + 1]) % mod + mod) % mod; }
int gethash2(int l, int r) { return ((hsh2[l] - hsh2[r+1] * pw[r - l + 1]) % mod + mod) % mod; }
map<int, int> solve(string s) {
	int n = s.size();
	s = " " + s;
	hsh2[n + 1] = 0; pw[0] = 1;
	for (int i = 1; i <= n; ++i) hsh[i] = (base * hsh[i-1] + (s[i] - 'A' + 1)) % mod;
	for (int i = n; i >= 1; --i) hsh2[i] = (base * hsh2[i+1] + (s[i] - 'A' + 1)) % mod;
	for (int i = 1; i <= n; ++i) pw[i] = 1LL * pw[i-1] * base % mod;
	map<pii, node, greater<pii>> mp; map<int, int> ans;
	auto tryadd = [&](pii a, node b) -> void {
		if (mp.count(a)) mp[a].v += b.v;
		else mp[a] = b;
	};
	for (int i = 1; i <= n; ++i) {
		int l = 0, r = min(i-1, n-i) + 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (gethash(i - mid, i + mid) == gethash2(i - mid, i + mid)) l = mid + 1;
			else r = mid;
		}
		--r;
		int val = gethash(i - r, i + r);
		tryadd({r * 2 + 1, val}, {i - r, i + r, 1});
	}
	for (int i = 1; i < n; ++i) {
		int l = 1, r = min(i, n-i);
		if (s[i] != s[i+1]) continue;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (gethash(i - mid + 1, i + mid) == gethash2(i - mid + 1, i + mid)) l = mid + 1;
			else r = mid;
		}
		--r;
		int val = gethash(i - r + 1, i + r);
		tryadd({r * 2, val}, {i - r + 1, i + r, 1});
	}
	while (!mp.empty()) {
		auto u = mp.begin();
		auto [len, val] = u->first;
		auto [l, r, cnt] = u->second;
		mp.erase(u);
		ans[val] = cnt;
		if (len > 2) {
			val = gethash(l + 1, r - 1);
			tryadd({len - 2, val}, {l + 1, r - 1, cnt});
		}
	}
	return ans;
}
signed main() {
	string s, b; cin >> s >> b;
	map<int, int> x = solve(s), y = solve(b);
	int ans = 0;
	for (const auto [i, j] : x) {
		if (y.count(i)) ans += 1LL * j * y[i];
	} write(ans, '\n');
	return 0;
}

qwqwqwqwqwq

2024/7/18 12:01
加载中...