自动搬运

查看原文

来自洛谷，原作者为

	kevin1616 HNCS 九年级 OIer || MC 1年萌新，PVZ 8年高玩 || 互关请私信 || 给我发接龙的全部拉黑

搬运于2025-08-24 22:58:14，当前版本为作者最后更新于2024-05-19 16:55:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

审题

给定一个字符串，求该字符串的两个子串是否一样。

方法

【暴力】对于一个字符串，我们将它的两个子串截取出来，再判断是否一样。由于判断的时间复杂度为 $O(len)$，故最终时间复杂度为 $O(len\times m)$，其中 $len$ 是字符串的长度。该算法无法通过本题。

【字符串哈希】可以发现判断字符串一样的复杂度可以通过字符串哈希优化为 $O(1)$，故最终时间复杂度为 $O(len+m)$，可以通过本题。

思路

首先求出字符串的前缀哈希值。通过以下代码实现：

for(int i = 1;i < s.size();i++){
  hs[i] = hs[i - 1] * 113 + s[i];
  pw[i] = pw[i - 1] * 113;
}

这边推荐使用质数作为进制数，这样可以更加避免哈希冲突。

然后我们将所求划分为一个子问题，即在区间中子串的哈希值是否相等。我们举一个例子：例如 $114514$ 这个数，我们要求从第 $2$ 位到第 $4$ 位组成的数，显而易见为 $1145-1000=145$。此时发现答案为 $hs_4-hs_1\times10^3$。所以得出，对于区间 $l$ 到 $r$，子串的哈希值为 $hs_r-hs_{l-1}\times base^{r-l+1}$。最后判断这两个值相等即可。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int q;
unsigned long long hs[1000005];
unsigned long long pw[1000005];
unsigned long long get_sizeHash(int a,int b){ //区间中子串的哈希值
    return hs[b] - hs[a - 1] * pw[b - a + 1];
}
int main(){
    cin >> s;
    s = " " + s;
    pw[0] = 1; //次方的初始化
    for(int i = 1;i < s.size();i++){
        hs[i] = hs[i - 1] * 113 + s[i]; //前缀哈希值
        pw[i] = pw[i - 1] * 113; //113的次方
    }
    cin >> q;
    while(q--){
        int a,b,x,y;
        cin >> a >> b >> x >> y;
        if(get_sizeHash(a,b) == get_sizeHash(x,y)) cout << "Yes\n"; //判断两个区间中子串的哈希值是否相等
        else cout << "No\n";
    }
    return 0;
}

不抄题解，从我做起！