/*
http://acm.hdu.edu.cn/showproblem.php?pid=2846
Repository 字典树变式
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
using namespace std;

typedef struct node{
	int no;
	int count;
	struct node* next[27];
	node(int _count = 0)
	{
		count = _count;
		no = -1;
		int i;
		for(i = 0 ; i < 27 ; i ++)
		{
			next[i] = NULL;
		}
	}
}Trie;

void insertNode(Trie* trie , char* s,int noo)
{
	Trie* t = trie;
	int i = 0;
	while(s[i] != '\0')
	{
		int tmp = s[i]-'a';
		if(t->next[tmp] == NULL)
		{
			t->next[tmp] = new node(0);
		}
		t = t->next[tmp];
		if(t->no != noo) // noo 做标记 增加数量
		{
			t->count ++;
			t->no = noo;
		}
		i ++;
	}

}

int func(Trie* trie,char s[])
{
	Trie* t = trie;
	Trie* tpre;
	int i = 0;
	while(s[i] != '\0')
	{
		int tmp = s[i]-'a';
		if(t->next[tmp] == NULL)
		{
			return 0;
		}
		tpre = t;
		t = t->next[tmp];
		i ++;
	}
	return t->count;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int n , m ;
	int i , j ;
	scanf("%d",&n);
	char stmp[21];
	Trie* trie = new node(0);
	for(i = 0 ; i < n ; i ++)
	{
		scanf("%s",stmp);
		int len = strlen(stmp);
		/*
			这里对于stmp = "abc" 分为 abc，bc，c这3个字符串插入 
				一次插入后如下图
					   root
					  / |  					a   b   c 
				   /    |
				  b     c
				 /
				c
			每次都这样处理， 相应字符的count 会加上去，最后统计count就行了
		*/
		for(j = 0;j < len ;j ++)
		{
			insertNode(trie , stmp+j , i);
		}
	}

	scanf("%d" , &m) ;
	for(i = 0 ; i < m ; i ++)
	{
		scanf("%s",stmp);
		printf("%d\n" , func(trie,stmp) ) ;
	}
	return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。