HASH 球调
  • 板块CF113B Petr#
  • 楼主kimi0705
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/2 19:11
  • 上次更新2024/8/2 20:26:54
查看原帖
HASH 球调
637788
kimi0705楼主2024/8/2 19:11
#include <bits/stdc++.h>
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 1e7 + 9;
const int base = 26;
const int mod[2] = {1000000007, 998244353};
int base_pow[2][N] = {{1, 1}};
string s, sb, se;
pii SB, SE;
pii Hash[N];

set <pii> S;

int qpow (int x, int y, int mod) {
	if (y == 1) return x;
	int res = qpow (x, y / 2, mod); res = res * res % mod;
	return y & 1 ? res * x % mod : res;
}

int HASH (string s, int type) {
	int res = 0;
	for (int i = 0; i < s.size(); i++) 
		res += (s[i] - 'a') * base_pow[type][i];
	return res;
}
int ny (int a, int type) { return qpow (a, mod[type] - 2, mod[type]); }
pii query (int l, int r) {
	return { (Hash[r].first - Hash[l].first) * ny(r - l + 1, 0),
	(Hash[r].second - Hash[l].second) * ny(r - l + 1, 1) };
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#ifdef kimi
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  for (int i = 1; i <= 2000; i++) base_pow[0][i] = base_pow[0][i - 1] * base % mod[0];
  for (int i = 1; i <= 2000; i++) base_pow[1][i] = base_pow[1][i - 1] * base % mod[1];
  cin >> s >> sb >> se;
  for (int i = 0; i < s.size(); i++) 
	Hash[i].first = (i == 0) ? s[i] - 'a' : Hash[i - 1].first + (s[i] - 'a') * base_pow[0][i],
	Hash[i].second = (i == 0) ? s[i] - 'a' : Hash[i - 1].second + (s[i] - 'a') * base_pow[1][i];
  SB = {HASH(sb, 0), HASH(sb, 1)};
  SE = {HASH(se, 0), HASH(se, 1)};
  cout << SB.first << ' ' << SB.second << '\n';
  cout << SE.first << ' ' << SE.second << '\n';
  int maxx = max(se.size(), sb.size());
  for (int i = 0; i < s.size(); i++) {
  	for (int j = i + maxx - 1; j < s.size(); j++) {
  		if (query (i, i + sb.size() - 1) == SB && query (j - se.size() + 1, j) == SE) {
  			S.insert (query(i, j));
  		}
  	}
  }
  cout << S.size () << '\n';
  cerr << "Time used = " << (double)clock() / CLOCKS_PER_SEC << '\n';
  return 0;
}
2024/8/2 19:11
加载中...