本文主要是介绍兔子与兔子（算法竞赛进阶指南 P62，字符串 Hash），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
兔子与兔子
二.题目大意：
给一个串 s.
q 次询问，每次询问给出 l1, r1, l2, r2.
让你判断 s[l1, r1] == s[l2, r2] ?
三.分析：
感觉这个挺 nb 的，就写个博客（题解请见书）纪念一下.
字符串 Hash 可以 O（N） 预处理字符串的前缀哈希值，O（1）时间查询任意子串哈希值.
四.代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;const int M = (int)1e6;
const int mod = 99991;
const int inf = 0x3f3f3f3f;char s[M + 5];
ull p[M + 5];
ull sum[M + 5];void work()
{p[0] = 1;sum[0] = 0;int len = strlen(s + 1);for(int i = 1; i <= len; ++i){p[i] = p[i - 1] * 131;sum[i] = sum[i - 1] * 131 + s[i] - 'a' + 1;}
}ull get_h(int l, int r)
{return sum[r] - sum[l - 1] * p[r - l + 1];
}int main()
{scanf("%s", s + 1);work();int q;scanf("%d", &q);int l1, r1, l2, r2;while((q--) > 0){scanf("%d %d %d %d", &l1, &r1, &l2, &r2);if(get_h(l1, r1) == get_h(l2, r2))printf("Yes\n");elseprintf("No\n");}return 0;
}
这篇关于兔子与兔子（算法竞赛进阶指南 P62，字符串 Hash）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
