MinLand @ 2024-10-10 14:17:22
record
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
using ull = unsigned ll;
int T;
namespace awa {
const int N = 1e5 + 1145, Z = 65, S = 3e6 + 114;
int n, q, idx;
int t[N][Z], cnt[N];
int get_num(char c) {
if (isdigit(c))
return c - '0' + 1;
bool isCapital = false;
if (isupper(c))
c = tolower(c), isCapital = true;
return c - 'a' + (isCapital ? 26 : 0) + 1;
}
//a z ~~ A Z
//11 36~~37 62
// 0 1 2 3
// 1 2 3 4
void insert(char str[]) {
int p = 0, len = strlen(str);
for (int i = 0; i < len; i++) {
int c = get_num(str[i]);
if (!t[p][c])
t[p][c] = ++idx;
p = t[p][c];
cnt[p]++;
}
}
int find(char str[]) {
int p = 0, len = strlen(str);
for (int i = 0; i < len; i++) {
int c = get_num(str[i]);
if (!t[p][c])
return 0;
p = t[p][c];
}
return cnt[p];
}
char s[S];
void solve() {
n = 0, q = 0, idx = 0;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= Z; j++)
t[i][j] = 0;
for (int i = 1; i <= n; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s);
}
for (int i = 1; i <= q; i++) {
scanf("%s", s);
printf("%d\n", find(s));
}
}
}
int main() {
cin >> T;
while (T--) {
awa::solve();
}
return 0;
}
N开成3e6之后没问题。 但是数据最多不是1e5?
by Zcras @ 2024-10-16 16:39:07
t[N][Z],按照正常理解应该是t[S][Z]