ZY_202301005129 @ 2024-11-16 00:42:00
首先是我的代码,
// P8306 【模板】字典树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <bits/stdc++.h>
using namespace std;
struct node
{
int s[62] = {0};//前26个存储字母,后面的储存数字
int end=0;
int num=0;
}t[3000005];
int n, m;
void add(string a,node *t,int&p)
{
int now=0;
for (auto i = a.begin();i != a.end();i++)
{
int j;
if (*i >= '0' && *i <= '9')
j = 52 + *i - '0';
else if (*i >= 'a' && *i <= 'z')
j = *i - 'a';
else j = *i - 'A' + 26;
if (!t[now].s[j])
t[now].s[j] = ++p;
now = t[now].s[j];
if (i + 1 != a.end())
t[now].num++;
}
t[now].end++;
}
int find(string a,node*t)
{
int now = 0;
int sum;
for (auto i = a.begin();i != a.end();i++)
{
int j;
if (*i >= '0' && *i <= '9')
j = 52 + *i - '0';
else if (*i >= 'a' && *i <= 'z')
j = *i - 'a';
else j = *i - 'A' + 26;
if (!t[now].s[j])
return 0;
else now = t[now].s[j];
//sum = t[now].num;
//if (i + 1 == a.end())
//sum += t[now].end;
}
return t[now].end+ t[now].num;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//取消同步流
int x;cin >> x;
while (x--)
{
int p=0;
cin >> n >> m;
memset(t, 0, sizeof(t));
for (int i = 1;i <= n;i++)
{
string a;cin >> a;
add(a,t,p);
}
for (int i = 1;i <= m;i++)
{
string a;cin >> a;
cout << find(a,t) << "\n";
}
}
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
// 入门使用技巧:
// 1. 使用解决方案资源管理器窗口添加/管理文件
// 2. 使用团队资源管理器窗口连接到源代码管理
// 3. 使用输出窗口查看生成输出和其他消息
// 4. 使用错误列表窗口查看错误
// 5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
// 6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件
其次是一个题解的代码,这个代码甚至用的是手动置0,我原本是用局部变量初始化来规避生成时间,本来能过第二点,结果模仿ta的代码后第二个都过不了了......
#include<bits/stdc++.h>
using namespace std;
int T, q, n, t[3000005][65], cnt[3000005], idx;
char s[3000005];
int getnum(char x) {
if (x >= 'A' && x <= 'Z')
return x - 'A';
else if (x >= 'a' && x <= 'z')
return x - 'a' + 26;
else
return x - '0' + 52;
}
void insert(char str[]) {
int p = 0, len = strlen(str);
for (int i = 0;i < len;i++) {
int c = getnum(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 = getnum(str[i]);
if (!t[p][c])
return 0;
p = t[p][c];
}
return cnt[p];
}
int main() {
scanf("%d", &T);
while (T--) {
for (int i = 0;i <= idx;i++)
for (int j = 0;j <= 122;j++)
t[i][j] = 0;
for (int i = 0;i <= idx;i++)
cnt[i] = 0;
idx = 0;
scanf("%d%d", &n, &q);
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));
}
}
return 0;
}
by lhz2022 @ 2024-11-17 23:34:39
@ZY_202301005129
你说有没有一种可能,就是要手动清0
memset又不是O(1)的
by ZY_202301005129 @ 2024-11-19 15:39:06
@lhz2022搞不懂,用了memset速度难道还比手动慢吗?那memset存在的意义是什么
by ZY_202301005129 @ 2024-11-19 16:31:08
搞清楚错因了,供大家参考一下挨: 1.清零操作是一个非常消耗性能的事,但是不清不行,所有根据上一次所累积到的p值为清零的界限,手动和memset的区别不大 2.使用取消同步流可能会导致输出错误(没学,搞不太懂)
我分析的原因大致就是这样,有讲错的地方请指正