兔子与兔子

链接

给出一个字符串,和两个下标l,r

怎么快速找到哈希值呢

我们通过预处理,将某个字符串转化为其他进制数

以十进制数为例 假设字符串12345678 我希望得到678的哈希值,我该怎么算呢

我们只需要用12345678-12345000就行了

其他进制同理

具体计算类似前缀和,用8处的预存好的哈希减去5处预存哈希的base^3倍即可

代码如下:

#include<iostream>
#include<vector>
using namespace std;
#define ull unsigned long long
const int base = 2333;
vector<ull>h, b;

void solve() {
	int l1, r1, l2, r2;
	cin >> l1 >> r1 >> l2 >> r2;
	ull res1 = h[r1] - h[l1-1] * b[r1 - l1 + 1];
	ull res2 = h[r2] - h[l2-1] * b[r2 - l2 + 1];
	if (res1 == res2) cout << "Yes\n";
	else cout << "No\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string str;
	cin >> str;
	int n = str.size();
	h.assign(n + 1, 1);
	b.assign(n + 1, 1);
	for (int i = 1;i <= n;++i) {
		b[i] = b[i - 1] * base;
		h[i] = h[i - 1] * base + str[i-1] - 'a' + 1;
	}
	int t;
	cin >> t;
	while (t--) solve();
}

时间复杂度:O(max(n,t))

空间复杂度:O(n)