Trong bài này ta sẽ chia xâu S thành các phần có độ dài là block và cho vào trie -> xử lí những
truy vấn có độ dài <= block.
Còn những truy vấn có độ dài >= block thì sao?? Vì nó có tối đa là $q \div block$ truy vấn như thế nên
ta chỉ cần dùng hashing để đếm thôi.
Tại sao ta lại chia thành 2 phần như vậy??
Ta nhận thấy, ở phần thứ nhất, điều kiện kiên quyết nhất
ảnh hưởng đến "mức độ thành công" của nó nằm ở bộ nhớ, nếu những truy vẫn có độ dài là block thì bộ
nhớ đâu đó tầm: $(8 \times 26 + 4)\times n \times block \div 2^{20} $ MB.
Trong đó:
- 8 là bit của 1 con trỏ.
- 4 là bit của biến đếm cnt.
- 26 là số lượng kí tự khác nhau.
Vì đề chỉ giới hạn 768 MB nên ta dễ dàng hoặc không để tính được block nằm khoảng 34.
Tuy nhiên phần thứ 2 lại bị ảnh hưởng chính bởi số lượng truy vấn có độ dài >= block, có tối đa
khoảng $q \div block$ truy vấn như vậy.
Đến đây ta thấy rằng trong phần 1 block tỉ lệ thuận tuy nhiên trong phần 2 block tỉ lệ nghịch, nên
ta mới có thể chia căn như vậy, phần còn lại ở đây là tìm giá trị block thích hợp. Tuy nhiên vì phần 1
bị giới hạn mạnh bởi bộ nhớ nên là block ở đây sẽ tầm 33.
Độ phức tạp không gian: $O(212 \times n \times block + 16 \times n)$.
Độ phức tạp thời gian: ... khó tính lăms nhưng tóm gọn là tầm $O(n \times block + max(q, q \div block \times (n - block)))$.
code:
```
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
constexpr ll base_1 = 29;
constexpr ll base_2 = 31;
constexpr int MOD_1 = 1e9 + 7;
constexpr int MOD_2 = 1e9 + 9;
constexpr int maxn = 1e5;
constexpr int bl = 33;
struct Trie{
struct Node{
Node *child[26];
int cnt;
Node(){
for(int i = 0; i < 26; ++i) child[i] = nullptr;
cnt = 0;
}
};
int cur;
Node *root;
Trie() : cur(0){
root = new Node();
};
void build(const string & s, int l, int r){
Node *p = root;
for(int i = l; i <= r; ++i){
int c = s[i] - 'a';
if(p->child[c] == nullptr) p->child[c] = new Node();
p = p->child[c];
++p->cnt;
}
}
int get(const string & a){
Node *p = root;
for(int x : a){
int c = x - 'a';
if(p->child[c] == nullptr) return 0;
p = p->child[c];
}
return p->cnt;
}
};
int n, m;
string s;
pair<ll, ll> val[maxn + 5], pw[maxn + 5];
Trie trie;
void pro_1(const string & a){
cout << trie.get(a) << '\n';
}
void pro_2(const string & a){
int size_ = a.size(), cnt = 0;
pair<ll, ll> res = {0, 0};
for(int i = 0; i < size_; ++i){
res.fi = (res.fi * base_1 + a[i] - 'a' + 1) % MOD_1;
res.se = (res.se * base_2 + a[i] - 'a' + 1) % MOD_2;
}
for(int i = 1; i <= n - size_ + 1; ++i){
int cur_1 = (val[i + size_ - 1].fi - val[i - 1].fi * pw[size_].fi % MOD_1 + MOD_1) % MOD_1;
int cur_2 = (val[i + size_ - 1].se - val[i - 1].se * pw[size_].se % MOD_2 + MOD_2) % MOD_2;
if(cur_1 == res.fi && cur_2 == res.se){
++cnt;
}
}
cout << cnt << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#define NAME "t"
if(fopen(NAME ".INP", "r")){
freopen(NAME ".INP", "r", stdin);
freopen(NAME ".OUT", "w", stdout);
}
cin >> s;
n = s.size();
s = ' ' + s;
pw[0] = {1, 1};
for(int i = 1; i <= n; ++i){
val[i].fi = (val[i - 1].fi * base_1 + s[i] - 'a' + 1) % MOD_1;
val[i].se = (val[i - 1].se * base_2 + s[i] - 'a' + 1) % MOD_2;
pw[i].fi = pw[i - 1].fi * base_1 % MOD_1;
pw[i].se = pw[i - 1].se * base_2 % MOD_2;
}
for(int i = 1; i <= n; ++i){
trie.build(s, i, min(n, i + bl - 1));
}
cin >> m;
for(int i = 1; i <= m; ++i){
string a;
cin >> a;
if(a.size() <= bl){
pro_1(a);
}else pro_2(a);
}
return 0;
}
```
kh0i
Created at
9 likes
nhanmuaairi
Created at
2 likes