题目描述

题目链接

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

输入样例：

1
2
3
4
5
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

1
2
3
Yes
No
Yes

算法1

(字符串哈希) $O(n)$

字符串匹配类型的题目可以考虑使用 KMP 算法，但是KMP算法是 $O(n^2)$ 的时间复杂度，在面对较大数据范围时，将会超时，因此在此题中应该考虑使用另外的解题方法

由于题目需要求两个范围内的字符串是否相等，那么很容易联想到前缀和，因为前缀和算法是可以在 O(1) 的时间内得到两个范围内的和，因此如果能够采用某种方法将字符串映射称为一串数字，那么通过前缀和的思维方式，也可以得到相应的结果

因此，可以尝试将字符串映射称为一个数字，将整个字符串映射成为某个 P 进制的数，那么通过预处理，我们可以在 O(1) 的时间之内求得两个位置之间的数字，根据数字是否相等就能够匹配出是否两个范围内的字符串相等

技巧

  • 一般选择 P = 131 或 P = 13331
  • 由于字符串的 P 进制数可能会极大，因此需要对其进行取模，一般使用 无符号64位整型来存储，这样的话即使越界溢出，那么就相当于取模运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

const int N = 100010, P = 131;
typedef unsigned long long ULL;
ULL h[N], p[N];
int n, m;
char str[N];

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);
    
    // 预处理
    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;
}