n2字符串hash被卡
查看原帖
n2字符串hash被卡
68189
lamkappa楼主2024/11/18 21:49

委屈,哭哭

#include <bits/stdc++.h>
#pragma GCC optimize(3)

#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
// 哈希表
// const int RANDOM = std::chrono::high_resolution_clock::now().time_since_epoch().count();
// template<typename K_T>
// struct Chash{
//     static std::hash<K_T> hash;
//     int operator()(K_T x)const{return hash(x)^RANDOM;}
// };
template<typename K_T, typename V_T, typename Hash = std::hash<K_T>>
using hash_table = __gnu_pbds::gp_hash_table<K_T, V_T, Hash>;

using namespace std;
using ll = long long;
using ull = unsigned long long;
// ull mul = 127;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1,s2;
    cin >> s1 >> s2;
    if(s1.size() > s2.size()) swap(s1, s2);

    // vector<ull> t1(s1.size() + 1), t2(s2.size() + 1);
    // for(int i=1; i<=s1.size(); i++){
    //     t1[i] = t1[i - 1] * mul + s1[i - 1];
    // }
    // for(int i=1; i<=s2.size(); i++){
    //     t2[i] = t2[i - 1] * mul + s2[i - 1];
    // }

    ull m = 1, t1 = 0, t2 = 0;
    hash_table<ull ,int> cnt1;
    hash_table<ull ,int> cnt2;
    for(int len = 1; len <= s1.size(); len++){
        cnt1.clear(); cnt2.clear();

        t1 = (t1 << 7) - t1 + s1[len - 1];
        ull h = t1;
        for(int i=0; i + len - 1 < s1.size(); i++){
            cnt1[h]++;
            if(i + len < s1.size()){
                h -= s1[i] * m;
                h = (h << 7) - h + s1[i + len];
            }
        }

        t2 = (t2 << 7) - t2 + s2[len - 1];
        h = t2;
        bool fl = false;
        for(int i=0; i + len - 1 < s2.size(); i++){
            auto itr = cnt1.find(h);
            if(itr != cnt1.end()){
                fl = true;
                if(itr->second == 1){
                    cnt2[h]++;
                }
            }
            if(i + len < s2.size()){
                h -= s2[i] * m;
                h = (h << 7) - h + s2[i + len];
            }
        }

        if(!fl) break;

        for(const auto[k, v] : cnt2){
            if(v == 1){
                cout << len << '\n';
                return 0;
            }
        }

        m = (m << 7) - m;
    }
    cout << -1;

    return 0;
}

呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜 TLE on 158

2024/11/18 21:49
加载中...