Aakkosetsumussa @ 2023-06-29 10:09:08
#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
#define fur(y) for(inr i=1;i<=y;i++)
#define fru(i,s,e) for(inr i=s;i<=e;i++)
#define frd(i,s,e) for(inr i=s;i>=e;i--)
#define el <<endl
#define sp <<" "<<
inr n,m,q,T;
inr trie[500005][205],num[500005]= {0},pos=1;
inline void Insert(string str) {
inr p=0;
for(inr i=0; i<str.size(); i++) {
inr n=str[i];
if(trie[p][n]==0) trie[p][n]=pos++;
p=trie[p][n];
num[p]++;
}
}
inline inr find(string str) {
inr p=0;
for(inr i=0; i<str.size(); i++) {
inr n=str[i];
if(trie[p][n]==0) return 0;
p=trie[p][n];
}
return num[p];
}
string ch;
main() {
ios::sync_with_stdio(false);
cin>>T;
while(T--) {
cin>>n>>q;
for(inr i=0; i<=pos; i++)
for(inr j=0; j<=200; j++) trie[i][j]=0;
for(inr i=0; i<=pos; i++) num[i]=0;
pos=1;
for(inr i=1; i<=n; i++) {
cin>>ch;
Insert(ch);
}
for(inr i=1; i<=q; i++) {
cin>>ch;
cout<<find(ch)<<endl;
}
}
return 0;
}
by Muh_Yih @ 2023-07-12 16:43:13
数组开小了(我也是这个问题,调了一天才发现())
by Muh_Yih @ 2023-07-12 16:43:50
注意到
输入字符串的总长度不超过
3 \times 10^6
by Muh_Yih @ 2023-07-12 16:46:08
另外数组开int
类型足够,long long
会太大而 CE
by Muh_Yih @ 2023-07-12 16:46:27
AC 记录
by Muh_Yih @ 2023-07-12 21:01:03
@Aakkosetsumussa
by Aakkosetsumussa @ 2023-07-13 08:05:35
@Muh_Yih
大佬不用了,我后来把数组开大然后把string换成char[]就过了()
by Muh_Yih @ 2023-07-13 18:55:33
@Aakkosetsumussa 是这样(不过其实用string
也可以,关键是数组大小)