When I was trying to solve 1968G2，I followed tutorial but replaced Z function with double hash. However, I got TLE. So is there any complexity difference between double hash and Z function? Or it's just slight efficiency different that causes TLE?

My code here:

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int t, n, l, r;
struct hash_string {
    string S;
    int mod, p;
    vector<long long> h;
    vector<long long> p_pow;
    hash_string() {}
    hash_string(int mod, int p) : mod(mod), p(p) {
        p_pow.emplace_back(1ll);
        h.emplace_back(0ll);
    }
    hash_string(string S, int mod, int p) : S(S), mod(mod), p(p), h(S.size() + 1), p_pow(S.size() + 1) { // 初始化字符串和模数
        h[0] = 0, p_pow[0] = 1;
        for (size_t i = 1; i <= S.size(); i++) {
            h[i] = (h[i - 1] * p + S[i - 1]) % mod;
            p_pow[i] = p_pow[i - 1] * p % mod;
        }
    }
    inline void insert(char c) { // 插入字符
        S += c;
        h.emplace_back((h.back() * p + c) % mod);
        p_pow.emplace_back(p_pow.back() * p % mod);
    }
    inline int hash_value(int l, int r) { // 查询哈希值
        return ((h[r] - h[l - 1] * p_pow[r - l + 1] % mod) % mod + mod) % mod;
    }
};
struct double_hash {
    string S;
    hash_string hash1, hash2;
    double_hash() {}
    double_hash(string S) : S(S) {
        hash1 = hash_string(S, (int)1e9 + 7, 1331);
        hash2 = hash_string(S, (int)1e9 + 9, 1331);
    }
    double_hash(string S, int mod1, int p1, int mod2, int p2) : S(S) { // 初始化，传入字符串和哈希模数
        hash1 = hash_string(S, mod1, p1);
        hash2 = hash_string(S, mod2, p2);
    }
    inline pair<int, int> hash_value(int l, int r) {
        return {hash1.hash_value(l, r), hash2.hash_value(l, r)};
    }
    inline bool equal(int l1, int r1, int l2, int r2) {
        return (hash1.hash_value(l1, r1) == hash1.hash_value(l2, r2) && hash2.hash_value(l1, r1) == hash2.hash_value(l2, r2));
    }
    inline void insert(char c) { // 插入字符
        hash1.insert(c), hash2.insert(c);
    }
};
std::string S;
inline void solve(void) {
    cin >> n >> l >> r >> S;
    double_hash H(S);
    vector<int> ans(n + 1);
    const int SQ = sqrt(n);
    auto check = [&](int len) -> int {
        int cnt = 1;
        if (len == 0) return 1e9;
        auto F = H.hash_value(1, len);
        for (int i = len; i + len - 1 < n; i++) {
            if (H.hash_value(i + 1, i + len) == F) {
                ++cnt, i = i + len - 1;
            }
        }
        return cnt;
    };
    for (int k = 1; k <= SQ; k++) {
        int L = 0, R = n / k, mid;
        while (L < R) {
            mid = (L + R + 1) >> 1;
            if (check(mid) >= k) {
                L = mid;
            } else {
                R = mid - 1;
            }
        }
        ans[k] = L;
    }
    for (int len = 1; len <= SQ; len++) {
        int k = check(len);
        ans[k] = max(ans[k], len);
    }
    for (int i = n - 1; i >= l; i--) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = l; i <= r; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}
inline void optimizeIO(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
}
int main(int argc, char const *argv[]) {
    optimizeIO(), cin >> t;
    while (t--) solve();
    return 0;
}