Nihao_A @ 2022-04-29 10:46:24
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50;
int f[N][70], cnt[N], idx = 1;
unordered_map<char, int>mymap;
void insert(string s)
{
int p = 1;
for (auto i : s)
{
int j = mymap[i];
if (f[p][j] == 0)f[p][j] = ++idx;
p = f[p][j];
cnt[p]++;
}
}
int search(string s)
{
int p = 1;
for (auto i : s)
{
int j = mymap[i];
if (f[p][j] == 0)return 0;
p = f[p][j];
}
return cnt[p];
}
int main()
{
int t;
int ans = 0;
for (char i = 'a'; i <= 'z'; i++)
mymap[i] = ans++;
for(char i='0';i<='9';i++)
mymap[i] = ans++;
for (char i = 'A'; i <= 'Z'; i++)
mymap[i] = ans++;
cin >> t;
while (t--)
{
memset(f, 0, sizeof f);
memset(cnt, 0, sizeof cnt);
idx = 1;
int n, m;
cin >> n >> m;
string s;
for (int i = 0; i < n; i++)
{
cin >> s;
insert(s);
}
while (m--)
{
cin >> s;
cout << search(s) << endl;
}
}
return 0;
}
by 编码落寞 @ 2022-04-29 11:16:18
@Nihao_A
你这二维数组开的太大,就会MLE
by Nihao_A @ 2022-04-29 14:41:14
@编码落寞 谢谢佬回复,是,但是我看题目说字符串总和长3e6,而且大小写字母+数字都有,所以才开了这么大,我试着缩小了后,它就re了。。。
by 编码落寞 @ 2022-04-29 14:58:22
@Nihao_A
这题数据范围应该不适合用二维数组
by Nihao_A @ 2022-04-29 15:22:13
@编码落寞 好吧,谢谢佬了,我再试试
by Dedaka @ 2022-04-29 17:03:40
@Nihao_A @编码落寞 3e6*70亲测可过 但不能用memset
by Nihao_A @ 2022-04-29 19:49:41
@Dedaka 啊,那请教一下佬,怎么把字典树恢复成最开始的样子呢?
by Dedaka @ 2022-04-29 19:51:46
比如说这样
for(int i=1;i<=ct;i++){//ct为节点数
v[i]=0;
for(int j=1;j<=67;j++){
t[i][j]=0;
}
}//暴力清空 qwq