知识点:字符串哈希
这个题,在学完字符串哈希之后就很简单了,几分钟写完,新学的字符串哈希就是把字符串映射成一个整数,O(n)处理完整个字符串,O(1)查询字串的hash值,求字符串前缀的哈希值的时候类似求前缀和,求字串的时候类似于求区间和,当然一点不一样,但是可以类比的记忆,
学这个东西,可以去b站看董晓老师的视频,讲的很清楚,比自己看李煜东的书有效率很多,反正我是学一个知识点先去查查董晓那里讲了没有,
- #include
-
- using namespace std;
-
- typedef unsigned long long ull;
-
- const int N = 1e6 + 5;
- const int P = 131;
-
- ull h[N], p[N];
- string s;
-
- void solve(int len) {
- h[0] = 0; p[0] = 1;
- for (int i = 1; i < len; i++) {
- p[i] = p[i - 1] * P;
- h[i] = h[i - 1] * P + s[i];
- }
- }
-
- ull get(int l, int r) {
- return h[r] - h[l - 1] * p[r - l + 1];
- }
-
- int main() {
- cin >> s;
- s = " " + s;
- solve((int) s.size());
- int m;
- cin >> m;
- while (m--) {
- int l1, r1, l2, r2;
- cin >> l1 >> r1 >> l2 >> r2;
- cout << (get(l1, r1) == get(l2, r2) ? "Yes": "No") << endl;
- }
- return 0;
- }