题目描述
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
样例
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
字符串哈希
字符串前缀哈希法
核心思想:
预处理所有前缀的哈希.
例如对字符串"ABCD"
h[1]对应前缀"A"的哈希值,h[3]对应前缀"ABC"的哈希.
如何定义前缀的哈希?
1.把字符串看成P进制数.且进制位从高倒低.
h[1] = A*P^0
h[3] = A*P^2 + B*P^1 + C*P^0
2.将P进制转换成十进制
可以把字符assii码作为对应数值.
P进制转换成的十进制可能很大,最后模上Q.
注意:
一般字符不能映射成0,防止出现前缀0的情况.比如把A映射成0,那么A,AAA,AAAA哈希值都是0.
不考虑冲突.(两个不同前缀哈希值相同的情况,假定我们的rp值很高-.-)
经验值:
P = 131 / 13331; Q = 2^(64)
应用:
常数时间内判断字串是否相等.
例如: 1 2 3 4
A B C D
求字串[3,4]也就是CD的哈希值.
h[2] = A*P^1 + B*P^0
h[4] = A*P^3 + B*P^2 + C*P^1 + C*P^0
[3,4]的哈希值:h[4] - h[2]*P^2 //把AB左移至高位
一般情况:
h[L,R] = h[R] - H[L-1]*P^(R-L+1)
时间复杂度
预处理O(n),查询O(1)
C++ 代码
/*
* 实现时因为Q = 2^64,h%Q->[0,2^64-1],恰好是unsigned long long 的值域,所以
*哈希值可以用unsigned long long 表示,溢出时高位舍去,自动实现取模运算
*/
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int Max_N = 1e5 + 10, P = 131;
int n, m;
char str[Max_N];
ull h[Max_N], p[Max_N]; //p[i]预处理p^i
ull get_hash(int l, int r)
{
return h[r] - h[l-1]*p[r-l+1];
}
int main()
{
scanf("%d%d%s",&n,&m,str+1);
p[0] = 1;
for( int i = 1; i <= n; i++ )
{
p[i] = P*p[i-1];
h[i] = h[i-1]*P + str[i];//直接用assii码作为字符映射 只要保证不映射0就行
}
while( m-- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if( get_hash(l1,r1) == get_hash(l2,r2) ) puts("Yes");
else puts("No");
}
return 0;
}