Select solution language
Write solution here.
Ta sẽ xử lí các truy vấn có cùng độ dài cùng một lúc bằng cách sử dụng Hash. Nhận thấy rằng
$\sum |T| \le 10^5$, nên ta chỉ cần xử lí tối đa $\sqrt{2 \cdot |T|}$ độ dài khác nhau của các truy vấn.
*Chứng minh:* $\displaystyle 1 + 2 + \dots + \sqrt{2 \cdot |T|} = \frac{\sqrt{2 \cdot |T|}(\sqrt{2 \cdot |T|} + 1)}{2} = \frac{2 \cdot |T| + \sqrt{2 \cdot |T|}}{2} \lt |T|$
Với mỗi độ dài, ta có thể sort các hash của các xâu con liên tiếp, sau đó dùng two pointers để đếm số lượng xâu con thỏa mãn.
Độ phức tạp: $O(\sqrt{(2 \cdot |T|)} * |S| + q * \log q)$.
Code mẫu:
```cpp
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 1e5 + 3;
struct Hash{
const ll base = 31;
const ll MOD = 1e9 + 3;
int n;
string s;
vector<ll> p, hash;
void precalc(int _n){
p[0] = 1;
for(int i = 1; i <= _n; ++i)
p[i] = (p[i - 1] * base) % MOD;
}
void init(string x){
n = x.size();
hash.resize(n + 2, 0);
p.resize(n + 2, 0);
precalc(n);
s = ' ' + x;
for(int i = 1; i <= n; ++i)
hash[i] = (hash[i - 1] * base + (s[i] - 'a' + 1)) % MOD;
}
ll get_hash(int l, int r){
return (hash[r] - hash[l - 1] * p[r - l + 1] + MOD * MOD) % MOD;
}
ll get_single_hash(string x){
ll res = 0;
for(int i = 0; i < sz(x); ++i)
res = (res * base + (x[i] - 'a' + 1)) % MOD;
return res;
}
} mim;
int n, ans[N], m;
string s;
vector<pair<ll, int>> q[N];
void solve(){
cin >> s;
mim.init(s);
n = sz(s);
s = ' ' + s;
cin >> m;
for(int i = 1; i <= m; ++i){
string t;
cin >> t;
q[sz(t)].push_back({mim.get_single_hash(t), i});
}
for(int i = 1; i <= n; ++i){
if(sz(q[i])){
vector<ll> v;
for(int k = i; k <= n; ++k)
v.push_back(mim.get_hash(k - i + 1, k));
sort(v.begin(), v.end());
sort(q[i].begin(), q[i].end());
int cur = -1, cnt = 0;
for(auto [hsh, id] : q[i]){
while(cur + 1 < sz(v) and v[cur + 1] <= hsh){
++cur;
cnt = (cur == 0 ? 1 : (v[cur] == v[cur - 1] ? cnt + 1 : 1));
}
ans[id] = (cur >= 0 and hsh == v[cur] ? cnt : 0);
}
}
}
for(int i = 1; i <= m; ++i)
cout << ans[i] << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
```
kh0i
Created at
7 likes