zzx0714 @ 2023-10-11 09:17:12
rt.
不知道为什么 Trie 的模板都能写挂了。。。
#include<bits/stdc++.h>
#define N 3000005
#define M 70
using namespace std;
int cnt=0;
inline int read()
{
int n=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') n=(n<<3)+(n<<1)+(c^48),c=getchar();
return n*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return;
}
inline int tonum(char c)
{
if(isupper(c)) return c-'A';
else if(islower(c)) return c-'a'+26;
else if(isdigit(c)) return c-'0'+52;
else exit(114514);
}
struct trie
{
int nex[N][M],exist[N];
inline void insert(char *s)
{
int p=0,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=tonum(s[i]);
if(!nex[p][c]) nex[p][c]=++cnt;
p=nex[p][c];
exist[p]++;
}
}
inline int find(char *s){ //0代表无,1代表有
int p=0,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=tonum(s[i]);
if(!nex[p][c]) return 0;
p=nex[p][c];
}
return exist[p];
}
inline void clear()
{
for(int i=0;i<=cnt;i++) for(int j=0;j<=69;j++) nex[i][j]=0;
for(int i=0;i<=cnt;i++) exist[i]=0;
}
}t;
char c[3000005];
int main()
{
int n,q,T;
T=read();
while(T--)
{
t.clear();
n=read(),q=read();
int i;
for(i=1;i<=n;i++)
{
cin>>c;
t.insert(c);
}
while(q--)
{
cin>>c;
write(t.find(c)),puts("");
}
}
return 0;
}
by 2024sdhkdj @ 2023-10-11 09:44:28
哪一题
by zzx0714 @ 2023-10-11 09:48:05
@qzhxy_hsb Link
by 2024sdhkdj @ 2023-10-11 10:01:05
@zzx0714 不是,多组数据你清空
by 2024sdhkdj @ 2023-10-11 10:04:39
你每次询问
by 2024sdhkdj @ 2023-10-11 10:05:24
不然
by zzx0714 @ 2023-10-11 12:52:03
@qzhxy_hsb cnt=0
以后 A 了,此帖终。