【求助】前缀哈希从0开始,为什么TLE了
查看原帖
【求助】前缀哈希从0开始,为什么TLE了
505669
_1xc7H楼主2024/9/29 19:33
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1000010;
ull base = 131;
ull h[N], po[N];
char s[N];

ull getHash(int l, int r)
{
    if(l == 0) return h[r];
    return h[r] - h[l - 1] * po[r - l + 1];
    //对于区间 l 到 r,子串的哈希值为 h_r - h_(l-1) * base^(r-l+1)
    //类比成进制数即可
}

int main()
{
    int m;
    cin >> s >> m;

    po[0] = 1;  //po[] 存储 base 的 i 次方
    // h[-1] = '';
    h[0] = (ull)s[0];
    for(int i = 1; i < strlen(s); i++)
    {
        h[i] = h[i - 1] * base + (ull)s[i];  // 存储的是 从 0 ~ i 的子区间的哈希值
        po[i] = po[i - 1] * base;
    }

    for(int i = 1; i <= m; i++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        l1--, r1--, l2--, r2--;
        if(getHash(l1, r1) == getHash(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
        // cout << getHash(l1, r1) << ' ' << getHash(l2, r2) << endl;
    }

    return 0;
}
2024/9/29 19:33
加载中...