模板 Trie樹

模板 Trie樹

code：

#include <iostream>
#include <cstdio>using namespace std;const int wx=20017;inline int read(){int sum=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}return sum*f;
}struct Trie{int tr[wx][27];int cnt;int flag[wx];void insert(char *s){int p=0;for(int i=0;s[i];i++){int k=s[i]-'a';if(!tr[p][k])tr[p][k]=++cnt;p=tr[p][k];}flag[p]=1;}bool query(char *s){int p=0;for(int i=0;s[i];i++){int k=s[i]-'a';if(!tr[p][k])return false;p=tr[p][k];}if(flag[p])return true;return false;}
}Trie;int n;
int m;
char c[wx];int main(){n=read();for(int i=1;i<=n;i++)scanf("%s",c),Trie.insert(c);m=read();for(int i=1;i<=n;i++)scanf("%s",c),printf("%d\n",Trie.query(c));return 0;
}