给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。输入格式
第一行包含整数 n 和 m,表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。
接下来 m 行,每行包含四个整数 l1,r1,l2,r2,表示一次询问所涉及的两个区间。
注意,字符串的位置从 1 开始编号。输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出
Yes
,否则输出No
。
每个结果占一行。数据范围
1≤n,m≤105
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2输出样例:
Yes
No
Yes
#include <iostream>
using namespace std;
const int N = 1000003, P = 13331;
typedef unsigned long long ll;
ll h1[N], p[N], h2[N];
ll get(ll (&h)[N], int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } //函数必须要有大括号
char a[N], b[N];
//get(l,r)是包括l,r的hash值
int main() { //在模板串中匹配模式串
int n, m;
cin >> n >> a + 1 >> m >> b + 1; //从1开始因为hash不能用0位置
p[0] = 1; //否则0000和00一样了
for (int i = 1; i <= m; ++i) {
p[i] = p[i - 1] * P; //P进制
h2[i] = h2[i - 1] * P + b[i]; //模板串hash值(长串)
}
for (int i = 1; i <= n; ++i) h1[i] = h1[i - 1] * P + a[i]; //模式串hash值
ll ans = get(h1, 1, n); //得到模板串的哈希值
for (int i = 1; i <= m - n + 1; ++i) { //遍历哈希 !长n串在长m串中走m-n+1次
if (ans == get(h2, i, i + n - 1)) { //如果在模式串中找到同样的hash值就输出
printf("%d ", i - 1);
}
}
return 0;
}