src/library.cpp - master - forthang/subarrays_task-forthang

src/library.cpp
64 строки2 KB
forthang
upd src/library.cpp
23 мар 2025, 23:18
23 мар 2025, 23:1823880e9
#include <vector>
#include <unordered_set>
#include <string>
#include <tuple>

using namespace std;

class Solution {
public:
    int longest_duplicate_subarray(const vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        
        const int base1 = 100007, mod1 = 1e9 + 7;
        const int base2 = 100043, mod2 = 1e9 + 9;
        
        vector<long long> prefix_hash1(n+1), prefix_hash2(n+1);
        vector<long long> power1(n+1, 1), power2(n+1, 1);
        

        for (int i = 0; i < n; ++i) {
            prefix_hash1[i+1] = (prefix_hash1[i] * base1 + nums[i]) % mod1;
            prefix_hash2[i+1] = (prefix_hash2[i] * base2 + nums[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
        
        auto get_hash = [&](int start, int len) -> pair<long long, long long> {
            long long hash1 = (prefix_hash1[start + len] - prefix_hash1[start] * power1[len]) % mod1;
            hash1 = (hash1 + mod1) % mod1;
            
            long long hash2 = (prefix_hash2[start + len] - prefix_hash2[start] * power2[len]) % mod2;
            hash2 = (hash2 + mod2) % mod2;
            
            return {hash1, hash2};
        };
        
        int low = 1, high = n - 1, result = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            bool found = false;
            unordered_set<string> seen;
            
            for (int i = 0; i <= n - mid; ++i) {
                auto [h1, h2] = get_hash(i, mid);
                string key = to_string(h1) + "," + to_string(h2);
                
                if (seen.count(key)) {
                    found = true;
                    break;
                }
                seen.insert(key);
            }
            
            if (found) {
                result = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
};