QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#703361 | #8334. Gene | XiCen | ML | 0ms | 0kb | C++20 | 1.1kb | 2024-11-02 17:39:02 | 2024-11-02 17:39:05 |
answer
#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
string s;
struct node {
unordered_map<char, int> son;
int end = 0;
} tree[12000005];
int tot = 0;
void insert(string word) {
int p = 0;
for (char i : word) {
// int idx = i - 'a';
if (!tree[p].son.count(i)) tree[p].son[i] = ++tot;
p = tree[p].son[i];
}
tree[p].end++;
}
int dfs(int now, int i, int kk) {
if (i == m) return tree[now].end;
int ans = 0;
if (tree[now].son[s[i]]) ans += dfs(tree[now].son[s[i]], i + 1, kk);
if (kk) {
for (int j = 0; j < 27; j++) {
if (j == s[i]-'a') continue;
if (tree[now].son.count('a'+j)) ans += dfs(tree[now].son['a'+j], i + 1, kk - 1);
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// 注意根据数据量调整N的大小
cin >> n >> q >> m >> k;
for (int i = 1; i <= n; i++) cin >> s, insert(s);
while (q--) {
cin >> s;
cout << dfs(0, 0, k) << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
6 4 4 1 kaki kika manu nana tepu tero kaka mana teri anan
output:
2 2 1 0