社区讨论
为什么样例第一个总是输出4,求调
P10470前缀统计参与者 2已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lyjd2mq1
- 此快照首次捕获于
- 2024/07/13 08:01 2 年前
- 此快照最后确认于
- 2024/07/13 08:24 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int t, n, q;
struct node{
int son[100];
int cnt;
} a[100005];
int get(char ch)
{
if (ch >= 'A' && ch <= 'Z')
{
return ch - 'A' + 27;
}
else if (ch >= 'a' && ch <= 'z')
{
return ch - 'a' + 1;
}
return ch - '0' + 53;
}
void insert(string s)
{
int len = s.size(), now = 1, cnt = 1;
for (int i = 0; i < len; i++)
{
// cout << now << ' ';
int num = get(s[i]);
if (a[now].son[num] == 0)
{
a[now].son[num] = ++cnt;
}
now = a[now].son[num];
if (i == len - 1)
{
a[now].cnt++;
}
}
// cout << endl;
return ;
}
void find(string s)
{
int len = s.size(), now = 1, ans = 0;
for (int i = 0; i < len; i++)
{
int num = get(s[i]);
if (a[now].son[num] == 0)
{
cout << ans << endl;
return ;
}
now = a[now].son[num];
ans += a[now].cnt;
// cout << ans << ' ';
}
cout << ans << endl;
return ;
}
/*void clearing(int x)
{
for (int i = 1; i <= x; i++)
{
for (int j = 0; j <= 62; j++)
{
a[i].son[j] = 0;
}
a[i].cnt = 0;
}
}
*/
signed main()
{
ios::sync_with_stdio();
cin.tie(0);cout.tie(0);
t = 1;
// cin >> t;
while (t--)
{
int n, q;
cin >> n >> q;
// clearing(id);
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
insert(s);
}
while (q--)
{
string s;
cin >> s;
find(s);
}
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...