#include using namespace std; //省代码写法 typedef unsigned long long ULL; const int N = 1000010, P = 131; //经验 或者 13331,取这两值的冲突概率低 int m; char str[N]; //字符串 ULL h[N], p[N]; //h表示某一个前缀的HASH值,h[k]表示的是前k个字母的HASH值,p[k]存储P^k mode 2^64 //计算部分字符串的HASH值 ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } //模板裸题啊! int main() { //输入+输出重定向 freopen("../AcWing/N6/138.txt", "r", stdin); //计算字符串前缀的HASH值,就是预处理 scanf("%s%d", str + 1, &m); //预处理 p[0] = 1; int n = strlen(str + 1);//因为我们把字符串放的时候放弃了索引0,所以这里strlen就也需要躲开0. for (int i = 1; i <= n; i++) { p[i] = p[i - 1] * P; h[i] = h[i - 1] * P + str[i]; } //然后根据公式计算两个区间的字符串HASH值是不是相同 while (m--) { int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); if (get(l1, r1) == get(l2, r2))puts("Yes"); else puts("No"); } //关闭文件 fclose(stdin); return 0; }