visit @ 2024-11-20 06:44:01
#include<bits/stdc++.h>
using namespace std;
int t,n,q,csl;
char cs[3000100];
char Trie[3001000][100];
bool ed[3000100];//标记结尾
int sum[3000100];//count(每个点对应几个字符串)
int m=1;
void biuld_Trie()
{
//建立Trie出现过就直接放,没出现过就让总数(下标位)+1 储存
//Trie大小与字符串总长度有关<=sum_len
//root=1 -> k
int k=1;
for(int i=1;i<=csl;i++)
{
char cc=cs[i];
int c=cc-'0';
if(!Trie[k][c])//从第k个点做向c的边
Trie[k][c]=++m;
k=Trie[k][c];
sum[k]++;
}
ed[k]=1;
}
int find_Trie()
{
int k=1;
for(int i=1;i<=csl;i++)
{
char cc=cs[i];
int c=cc-'0';
if(!Trie[k][c])
{
k=1;
break;
}
k=Trie[k][c];
}
return sum[k];
}
int main()
{
cin>>t;
while(t--)
{
memset(sum,0,sizeof(sum));
memset(Trie,0,sizeof(Trie));
memset(ed,0,sizeof(ed));
m=1;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>cs+1;
csl=strlen(cs+1);
biuld_Trie();
}
for(int i=1;i<=q;i++)
{
cin>>cs+1;
csl=strlen(cs+1);
cout<<find_Trie()<<endl;
}
}
return 0;
}
by 立柱已选162534 @ 2024-11-20 07:50:25
@visit 把char Trie
改为int Trie
并把endl
改为'\n'
即可。
999555 qp
by visit @ 2024-11-20 17:26:39
@立柱已选162534 好的谢谢,调好了,(好像数组还开大了,然后memset还得手动。。。 底子差了