P10468 兔子与兔子

kevin1616 · 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;
}

不抄题解，从我做起！