字典树（trie 树）

标准 Trie树的查找

       对于英文单词的查找，我们完全可以在内部结点中建立26个元素组成的指针数组。如果要查找a，只需要在内部节点的指针数组中找第0个指针即可(b=第1个指针，随机定位)。时间复杂度为O(1)。

      查找过程：假如我们要在上面那棵Trie中查找字符串bull (b-u-l-l)。

      (1) 在root结点中查找第('b'-'a'=1)号孩子指针，发现该指针不为空，则定位到第1号孩子结点处——b结点。

      (2) 在b结点中查找第('u'-'a'=20)号孩子指针，发现该指针不为空，则定位到第20号孩子结点处——u结点。

      (3) ... 一直查找到叶子结点出现特殊字符'$'位置，表示找到了bull字符串

      如果在查找过程中终止于内部结点，则表示没有找到待查找字符串。

      效率：对于有n个英文字母的串来说，在内部结点中定位指针所需要花费O(d)时间，d为字母表的大小，英文为26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式，因此时间复杂度降为了O(1)。但是如果是中文字，下面在实际应用中会提到。因此我们在这里还是用O(d)。 查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为O(d*n)。

      但是，当查找集合X中所有字符串两两都不共享前缀时，trie中出现最坏情况。除根之外，所有内部结点都自由一个子结点。此时的查找时间复杂度蜕化为O(d*(n^2))

struct node
{
	int next[27];
	int v;
	void init()
	{
		v=0;
		memset(next,-1,sizeof(next));
	}
};
node L[1000500];
string s[maxn];
int tot=0;//树中的节点数
void add(char s[],int len)
{
	int now=0;
	for(int i=0;i<len;i++)
	{
		int t=s[i]-'a';
		int next=L[now].next[t];
		if(next==-1)
		{
			next=++tot;
			L[next].init();
			L[now].next[t]=next;
		}
		now=next;
	}
	L[now].v=0;
}
int query(char s[],int len)//查询字符串是否存在
{
	int now=0;
	for(int i=0;i<len;i++)
	{
		int t=s[i]-'a';
		int next=L[now].next[t];
		if(next==-1)return -1;
		now=next;
	}
	return L[now].v;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 1000000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
struct Trie
{
	char ch[maxn];
	int left[maxn],right[maxn],cnt;
	//bool flag[maxn];
	int flag[maxn];
	Trie(){}
	void init()
	{
		cnt=1;
		left[0]=right[0]=0;
		flag[0]=0;
	}
	void add(const char*s)
	{
		int len=strlen(s),u=0,v;
		for(int i=0;i<len;i++)
		{
			for(v=left[u];v;v=right[v])
				if(ch[v]==s[i])break;
			if(v==0)
			{
				v=cnt++;
				ch[v]=s[i];
				flag[v]=0;
				right[v]=left[u];
				left[u]=v;
				left[v]=0;
			}
			flag[v]++;
			u=v;
		}
		//flag[v]=true;
	}
	int query(const char*s)
	{
		int len=strlen(s),u=0,v;
		for(int i=0;i<len;i++)
		{
			for(v=left[u];v;v=right[v])
				if(ch[v]==s[i])break;
			if(v==0)return false;
			u=v;
		}
		return flag[v];
	}
}tree;

int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    char s[14];
    int d;
    tree.init();
    while(gets(s)&&s[0]!='\0')
	{
		tree.add(s);
	}
	while(scanf("%s",s)!=EOF)
	{
		printf("%d\n",tree.query(s));
	}
    return 0;
}