【CCPC】CCPC 2023 Shenzhen Site G

Gene

#二分 #哈希 #字符串

题目描述

Let $s$ and $t$ be two strings with equal lengths $M$ . Define $f(s,t)={\sum }_{i=1}^M[s_i\ne t_i]$
You are given $N$ strings $s_1,s_2,\cdot \cdot \cdot ,s_N$ and a constant threshold $K$. Each of the string contains exactly$M$ lowercase letters. You need to perform the following queries $Q$ times:

$•$Given a string $t$ of length $M$ , calculate${\sum }_{i=1}^N[f(s_i,t)\le K]$

输入格式

The first line of the input contains four integers $N$, $Q$, $M$, and $K$ ($1\le N,Q\le 300,1\le M\le 60,000,1\le K\le 10).$
The $i-$th line of the next $N$ lines contains a single string si consisting exactly $M$ lowercase letters.
The $i-$th line of the next $Q$ lines contains a single string $t$ consisting exactly $M$ lowercase letters, indicating a query.

输出格式

For each query, output a single line contains a single integer, indicating the answer

样例 #1

样例输入 #1

6 4 4 1
kaki
kika
manu
nana
tepu
tero
kaka
mana
teri
anan

样例输出 #1

2
2
1
0

解法

解题思路

观察到$k\le 10$，因此我们可以对字符串进行哈希，枚举$n$个匹配串，然后每次二分出第$i(i\le k)$个不同的位置，如果能二分到最后的位置，那么这个匹配串就为合法的串了。

为了减少哈希碰撞，这里我们的哈希使用的是随机模数的哈希。

这样整体的时间复杂度在$O(mq+nklo{g}_{2}m)$

代码

mt19937_64 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());struct hash61 {hash61() {}static const uint64_t md = (1LL << 61) - 1;static uint64_t step;static vector<uint64_t> pw;uint64_t addmod(uint64_t a, uint64_t b) const {a += b;if (a >= md) a -= md;return a;}uint64_t submod(uint64_t a, uint64_t b) const {a += md - b;if (a >= md) a -= md;return a;}uint64_t mulmod(uint64_t a, uint64_t b) const {uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;uint64_t ret = (l & md) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;ret = (ret & md) + (ret >> 61);ret = (ret & md) + (ret >> 61);return ret - 1;}void ensure_pw(int sz) {int cur = (int)pw.size();if (cur < sz) {pw.resize(sz);for (int i = cur; i < sz; i++) {pw[i] = mulmod(pw[i - 1], step);}}}vector<uint64_t> pref;int n;template<typename T>hash61(const T& s) {n = (int)s.size();ensure_pw(n + 1);pref.resize(n + 1);pref[0] = 1;for (int i = 0; i < n; i++) {pref[i + 1] = addmod(mulmod(pref[i], step), s[i]);}}inline uint64_t operator()(const int from, const int to) const {assert(0 <= from && from <= to && to <= n - 1);return submod(pref[to + 1], mulmod(pref[from], pw[to - from + 1]));}
};
uint64_t hash61::step = (md >> 2) + rng() % (md >> 1);
vector<uint64_t> hash61::pw = vector<uint64_t>(1, 1);void solve() {int n, q, m, k;std::cin >> n >> q >> m >> k;std::vector<hash61>a(n + 1);for (int i = 1; i <= n; ++i) {std::string s;cin >> s; s = " " + s;a[i] = hash61(s);}while (q--) {std::string s;std::cin >> s;s = " " + s;auto b = hash61(s);int res = 0;for (int i = 1; i <= n; ++i) {int L = 1, R = m;for (int j = 1; j <= k; ++j) {int l = L, r = R, ans = -1;while (l <= r) {int mid = l + r >> 1;if (b(l, mid) == a[i](l, mid)) {ans = mid;l = mid + 1;}else {r = mid - 1;}}if (ans == -1) L++;else L = ans + 2;}if (L > m) ++res;else {if (b(L, m) == a[i](L, m)) ++res;}}std::cout << res << "\n";}}
signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}
}