smartbrisk @ 2024-08-07 08:19:43
模板题,#2#3#4#5都是TLE,但答案我下载下来发现都是对的,请求各位帮助,谢谢!
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int N = 3e6 + 10;
int pass[N], nexts[N][62], numNode = 1;
char str[N];
inline int charToInt(char ch)
{
return ch >= '0' && ch <= '9' ? ch - '0' :
(ch >= 'A' && ch <= 'Z' ? 10 + ch - 'A' : 36 + ch - 'a');
}
void addStr()
{
int node = 0, len = strlen(str);
for (int i = 0; i < len; ++i)
{
if (nexts[node][charToInt(str[i])] == -1)
{
nexts[node][charToInt(str[i])] = numNode++;
}
node = nexts[node][charToInt(str[i])];
++pass[node];
}
}
int query()
{
int node = 0, len = strlen(str);
for (int i = 0; i < len; ++i)
{
if (nexts[node][charToInt(str[i])] == -1)
{
return 0;
}
node = nexts[node][charToInt(str[i])];
}
return pass[node];
}
int main()
{
// freopen("trie.in", "r", stdin);
// freopen("trie.out", "w", stdout);
int T, n, q;
scanf("%d", &T);
while (T--)
{
memset(nexts, -1, sizeof(nexts));
memset(pass, 0, sizeof(pass));
numNode = 1;
scanf("%d%d", &n, &q);
while (n--)
{
scanf("%s", str);
addStr();
}
while (q--)
{
scanf("%s", str);
printf("%d\n", query());
}
}
//system("pause");
}
我把字符转化为数字的方法是:把
by _chicken_ @ 2024-08-07 10:15:00
@smartbrisk
TLE是因为memset超时了 改成for循环清空就行(应该
by smartbrisk @ 2024-08-07 10:46:54
我改对了,谢谢!