https://www.acwing.com/problem/content/140/
兔子与兔子的题解终于来了!
其实这个题目只需要哈希就能快速解决,
我直接用双哈希,
至于为什么我要用双哈希,
是因为单哈希太容易被卡,
原代码如下:
`
include [HTML_REMOVED]
using namespace std;
const int base = 1331, base1 = 1313; // 双哈希的进制
string s;
int m;
unsigned long long power[1000005], power1[1000005], hs[1000005], hs1[1000005]; // 哈希表与所需要的预处理
// 12行为什么我要用unsigned long long 是因为它必须自然流出
int main(){
cin >> s;
scanf(“%d”, &m);
s = “0” + s; // 不能让循环从零开始
power[0] = 1; // 这一步没有就错, 因为他是乘上去的
power1[0] = 1; // 与18行同理
for(int i = 1; i < s.size(); i){ // 做好哈希的预处理
hs[i] = hs[i-1] * base + s[i];
power[i] = power[i-1] * base;
hs1[i] = hs1[i-1] * base1 + s[i];
power1[i] = power1[i-1] * base1;
}
for(int i = 1; i <= m; i){
int l, r, l1, r1;
scanf(“%d%d%d%d”, &l, &r, &l1, &r1);
if(hs[r] - hs[l-1] * power[r - l + 1] == hs[r1] - hs[l1-1] * power[r1-l1+1] && hs1[r] - hs1[l-1] * power1[r-l+1] == hs1[r1] - hs1[l1-1] * power1[r1-l1+1]) // 29行是判断哈希值是否相等
__
printf(“Yes\n”);
else
printf(“No\n”);
}
return 0;
}
`