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;
}