学步园

/*
分析：
    字典树。自己的方法TLE了，百度下下，于是就加了个id。参考这儿：

http://hi.baidu.com/upc_acm/blog/item/3bf392c1c30569db51da4bc2.html

                                                  2012-07-05
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"

struct dic
{
	struct dic *child[26];
	int n;
	int id;
};
struct dic *root;

void insert(char *p,int limit,int k)
{
	struct dic *now,*newnode;
	int j;
	now=root;
	while(limit--)
	{
		if(now->child[*p-'a']!=NULL)
		{
			now=now->child[*p-'a'];
			if(now->id!=k)
			{
				now->id=k;
				now->n++;
			}
		}
		else
		{
			newnode=(struct dic *)malloc(sizeof(struct dic));
			for(j=0;j<26;j++)	newnode->child[j]=NULL;


			now->child[*p-'a']=newnode;
			now=newnode;
			now->id=k;
			now->n=1;
		}
		p++;
	}
}
int find(char *source)
{
	struct dic *now;
	int i;
	int len;
	len=strlen(source);
	now=root;
	for(i=0;i<len;i++)
	{
		if(now->child[source[i]-'a']!=NULL)
			now=now->child[source[i]-'a'];
		else return 0;
	}
	return now->n;
}
int main()
{
	int n,q;
	int i,l,j;
	int len;
	char *p;
	char str[22];
	
	root=(struct dic *)malloc(sizeof(struct dic));
	for(j=0;j<26;j++)	root->child[j]=NULL;
	root->n=0;
	root->id=-1;

	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s",str);
		len=strlen(str);
		p=str;
		for(l=0;l<len;l++)
		{
			insert(p,len-l,i);
			p++;
		}
	}

	scanf("%d",&q);
	for(i=0;i<q;i++)
	{
		scanf("%s",str);
		printf("%d\n",find(str));
	}

	return 0;
}