20

ad

ae

af

ag

ah

ai

aj

ak

al

ads

add

ade

adf

adg

adh

adi

adj

adk

adl

aes

5

b

a

d

ad

s

0

20

11

11

2

题解：字典树，把每个字符串的字串都用字典树保存下来，而且记录下每个子串的个数，可是要注意每个字符串可能有同样的字串。此时仅仅加一次。比如ababc,ab仅仅加一次

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

struct Node

{

	int id;

	int num;

	Node* next[26];

	Node()

	{

		id = -1;

		num = 0;

		for(int i = 0;i < 26;i++)

		{

			next[i] = NULL;

		}

	}

};

Node* root;

void insert(char* s,int k)

{

	int len = strlen(s);

	Node* p = root;

	for(int i = 0;i < len;i++)

	{

		if(p->next[s[i] - 'a'] == NULL)

		{

			Node* q = new Node();

			q->id = k;

			q->num = 1;

			p->next[s[i] - 'a'] = q;

		}

		p = p->next[s[i] - 'a'];

		if(p->id != k)

		{

			p->id = k; //该字符串中该子字符已经出现了

		    p->num++;  //该字串个数加一

		}

	}

}

int find(char* s)

{

	int len = strlen(s);

	Node* p = root;

	for(int i = 0;i < len;i++)

	{

		if(p->next[s[i] - 'a'] == NULL)

		{

			return 0;

		}

		p = p->next[s[i] - 'a'];

	}

	return p->num;

}

void del(Node*& p)

{

	for(int i = 0;i < 26;i++)

	{

		if(p->next[i] != NULL)

		{

			del(p->next[i]);

		}

	}

	delete p;

}

int main()

{

	int n;

	while(scanf("%d",&n) != EOF)

	{

		root = new Node();

		char s[100];

		for(int i = 0;i < n;i++)

		{

			scanf("%s",s);

			for(int j = 0;s[j] != '\0';j++)

			{

				insert(s + j,i);

			}

		}

		int q;

		scanf("%d",&q);

		for(int i = 0;i < q;i++)

		{

			scanf("%s",s);

			printf("%d\n",find(s));

		}

		del(root);

	}

	return 0;

 }