1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int MAXN = 50000; const int MAXM = 50000; const int MAXNODE = 500000; // 单词数*单词长度(最坏情况下节点数量) int tot, root, son[MAXNODE + 5][2]; int tag[MAXNODE + 5]; // 该节点存在几个单词 int cnt[MAXNODE + 5]; // 该节点下面一共存在几个单词 void clearNode(int nId) { for (int i = 0; i < 2; i++) son[nId][i] = 0; tag[nId] = 0; } void ins(const string &s) { int now = root; for (int i = 0; i < s.length(); i++) { int j = s[i] - '0'; if (!son[now][j]) { son[now][j] = ++tot; clearNode(tot); } now = son[now][j]; cnt[now]++; // 沿路加 } tag[now]++; // 只加一次 } int check(const string &s) { int res = 0; int now = root; for (int i = 0; i < s.length(); i++) { int j = s[i] - '0'; if (!son[now][j]) { return res; } now = son[now][j]; res += tag[now]; } return res - tag[now] + cnt[now]; } int n, m; string b[MAXN + 5]; string c[MAXM + 5]; int ans[MAXM + 5]; int main() { ios::sync_with_stdio(false); cin.tie(0); // 输入 cin >> n >> m; for (int i = 1; i <= n; i++) { int len; char x; b[i] = ""; cin >> len; while (len--) { cin >> x; b[i] = b[i] + x; } } for (int i = 1; i <= m; i++) { int len; char x; c[i] = ""; cin >> len; while (len--) { cin >> x; c[i] = c[i] + x; } } // 信息放入字典树 for (int i = 1; i <= n; i++) ins(b[i]); // 计算每个密码匹配哪些 for (int i = 1; i <= m; i++) cout << check(c[i]) << "\n"; return 0; }
- 1
信息
- ID
- 696
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 32
- 已通过
- 15
- 上传者