题海拾贝：P10468 兔子与兔子

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》

欢迎点赞，关注！

1、题目

P10468 兔子与兔子 - 洛谷

2、题解

#include<iostream>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
ULL p[N], a[N];
ULL P = 13331;
void getnum(string& s)
{	//注意第0位权重是1p[0] = 1;for (int i = 1;i <= s.size()-1;i++){a[i] = a[i-1] * P + s[i];p[i] = p[i-1]*P;//这个P是为了后面求取那一段的哈希值方便而来的}
}
ULL gethash(int l, int r)
{return a[r] - a[l - 1] * p[r + 1 - l];
}
int main()
{string s;cin >> s;s = " " + s;getnum(s);int m = 0;cin >> m;for (int i = 1;i <= m;i++){int l1=0, l2=0, r1=0, r2=0;cin >> l1 >> r1 >> l2 >> r2;ULL x=gethash(l1, r1);ULL y = gethash(l2, r2);if (x == y) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}