模板 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;

}
巴特西

模板 Trie树

最新文章

热门文章
