如何用字符串哈希解决匹配问题？

37.Acwing基础课第841题-简单-字符串哈希 题目描述 \(给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l_1,r_1,l_2,r_2，请你判断 [l_1,r_1]和 [l_2,r_2]这两个区间所包含的字符串子串是否完全相同。\) 字符串中只包含大小写英文字母和数字。 输入格式 \(第一行包含整数 n 和 m，表示字符串长度和询问次数。\) \(第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。\) \(接下来 m 行，每行包含四个整数 l_1,r_1,l_2,r_2，表示一次询问所涉及的两个区间。\) \(注意，字符串的位置从 1 开始编号。\) 输出格式 对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。 每个结果占一行。 数据范围 \(1≤n,m≤10^5\) 输入样例： 8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2 输出样例： Yes No Yes 代码： #include <iostream> using namespace std; typedef unsigned long long ULL;// 0 ~ 2^64 - 1, 溢出相当于取模 const int N = 1000010, P = 131;// P 取 131 或 13331 为经验值 int n, m; char str[N]; //h[i]表示前i项字符的哈希值，p[i]表示p的i次方 ULL h[N], p[N]; //求第l项和第r项之间的哈希值，包括l和r ULL get(int l, int r) { return h[r] - h[l-1]*p[r-l+1]; } int main() { scanf("%d%d%s", &n, &m, str+1);//从str[1]开始存字符 p[0] = 1; for(int i = 1; i <= n; i++) { p[i] = p[i-1] * P; h[i] = h[i-1] * P + str[i]; } 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"); } return 0; }