逆天双hash求条
查看原帖
逆天双hash求条
664034
_xxxxx_楼主2024/8/5 19:34

rt,样例没过,调的有点红温。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
string s;
int bas1 = 114, bas2 = 514, mod1 = 1e18 - 11, mod2 = 998244353;
int hsh1[N], hsh2[N];
int sba1[N], sba2[N];
// sum of bas 1/2
int mul1(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod1;
        a = a * a % mod1;
        b >>= 1;
    }
    return ans;
}
int mul2(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod2;
        a = a * a % mod2;
        b >>= 1;
    }
    return ans;
}
signed main()
{
    cin >> s;
    int len = s.size();
    s = "!" + s;
    sba1[0] = sba2[0] = 1;
    for(int i = 1; i <= len; i++)
    {
        hsh1[i] = (hsh1[i - 1] * bas1 % mod1 + s[i]) % mod1;
        hsh2[i] = (hsh2[i - 1] * bas2 % mod2 + s[i]) % mod2;
        sba1[i] = sba1[i - 1] * bas1 % mod1;
        sba2[i] = sba2[i - 1] * bas2 % mod2;
        // cout << hsh1[i] << " " << hsh2[i] << endl;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int l1, l2, r1, r2;
        scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
        bool f1=((hsh1[r1]-mul1(hsh1[l1-1], sba1[r1 - l1 + 1]) + mod1) % mod1 == (hsh1[r2]-mul1(hsh1[l2 - 1], sba1[r2 - l2 + 1]) + mod1) % mod1);
        bool f2=((hsh2[r1]-mul2(hsh2[l1-1], sba2[r1 - l1 + 1]) + mod2) % mod2 == (hsh2[r2]-mul2(hsh2[l2 - 1], sba2[r2 - l2 + 1]) + mod2) % mod2);
        // cout << (hsh1[r1]-mul1(hsh1[l1-1], sba1[r1 - l1 + 1]) + mod1) % mod1 << " " << (hsh1[r2]-mul1(hsh1[l2 - 1], sba1[r2 - l2 + 1]) + mod1) % mod1 << " " << (hsh2[r1]-mul2(hsh2[l1-1], sba2[r1 - l1 + 1]) + mod2) % mod2 << " " << (hsh2[r2]-mul2(hsh2[l2 - 1], sba2[r2 - l2 + 1]) + mod2) % mod2 << endl;
        if(f1 && f2) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
/*
148,818,971
*/
2024/8/5 19:34
加载中...