文章目录
题目描述
- 给定一个长度为
n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2， - 请你判断
[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。 - 字符串中只包含大小写英文字母和数字。
输入格式
- 第一行包含整数
n和m，表示字符串长度和询问次数。 - 第二行包含一个长度为
n的字符串，字符串中只包含大小写英文字母和数字。 - 接下来
m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。 - 注意，字符串的位置从
1开始编号。
输出格式
- 对于每个询问输出一个结果，如果两个字符串子串完全相同则输出
Yes，否则输出No。 - 每个结果占一行。
数据范围
1 ≤ n,m ≤ 10^5
基本思路
- 字符串哈希是一种非常常用的哈希方式，很多与字符串有关的算法问题都可以通过字符串哈希得到快速解决。
- 字符串哈希的方法被称为字符串前缀哈希法。在这种方法中，哈希表中下标为
i的单元存储着字符串中前i个字符构成的子串对应的哈希值。我们可以把字符串视为一个P进制的数字（这里的P一般取131或13331），不同的字符都转换为其对应的唯一的ASCII码。 - 通过上面的方式，对于任意一个字符串，我们都可以将其转换为一个
P进制的数字。这个数字一般都非常大，所以我们除了会使用最大的整型unsigned long long之外（这里使用无符号整型也可以起到溢出自动取模的作用，并且至少使用8个字节进行存储）会对该数据取模，模数为2的64次方。这样的取法使得发生哈希冲突的可能性最小。 - 在字符串哈希中有两个注意事项：首先，我们不能将任意字符映射为数字
0；其次，我们假设字符串哈希过程中都不会发生哈希冲突。 - 在字符串哈希中，只需要对一个字符串构建好了哈希表，则可以求出其中任意一个子串的哈希值。当子串的左端点下标为L，右端点下标为R时，该子串对应的哈希值为：
h[R]- h[L - 1] * p^(R-L+1)，具体的证明过程略。
实现代码
#include <iostream>
using namespace std;
// 分别表示字符串长度、询问次数和每一次的查询内容
int n, m;
int l1, r1, l2, r2;
// 分别表示字符串的长度上限和所采用的P值
const int N = 100010;
const int P = 131;
// 分别用于存储字符串、字符串对应的前缀哈希表以及P的幂次
char str[N];
unsigned long long hash_table[N], p_power[N];
int main(void)
{
// 输入部分，构建哈希表
cin >> n >> m;
p_power[0] = 1;
for(int i = 1; i <= n; ++ i)
{
cin >> str[i];
hash_table[i] = hash_table[i - 1] * P + str[i];
p_power[i] = P * p_power[i - 1];
}
// 查询部分
for(int i = 0; i < m; ++ i)
{
cin >> l1 >> r1 >> l2 >> r2;
unsigned long long hash1 = hash_table[r1] - hash_table[l1 - 1] * p_power[r1 - l1 + 1];
unsigned long long hash2 = hash_table[r2] - hash_table[l2 - 1] * p_power[r2 - l2 + 1];
if(hash1 == hash2) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}