QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#703361#8334. GeneXiCenML 0ms0kbC++201.1kb2024-11-02 17:39:022024-11-02 17:39:05

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 17:39:05]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-11-02 17:39:02]
  • 提交

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

result: