Problem A: Decoding

		ACM International Collegiate Programming Contest
		2003 Asia Regional Contest
		IIT Bombay
		Dec 7, 2003
	

A substitution cipher is a method used for encoding a plain text message. For every character c in the alphabet, a string f(c) is defined. A plain text message c1c2c3...cn is encoded by concatenating the strings f(c1)f(c2)f(c3)...f(cn) in the same order. You have to write a program, which given the substitution rules and a string, determines whether the string can be obtained by encoding some plain text message using the substitution rules.

Input

The input will consist of several test cases. The first line of each test case will specify n, the size of the alphabet for text messages. If n is 0, it indicates end of input. Assume that n is at most 10. The next n lines will specify the values of f(c) , one per line, for the n characters in the text alphabet. Assume that f(c) may contain at most 10 characters, each of which is from 'a' to 'z'. The next line will contain a single integer m, which is the number of strings to be tested with the given substitution rule. The next m lines will contain one string each with at most 10000 characters, each of which is from 'a' to 'z'.

Output

The output for each string tested is 1 if the string is an encoding of some string and 0 otherwise. The output should be written one per line, in the same order as the strings tested.

Sample Input

2
aba
ab
2
ababa
abaab
3
xyz
z
yyx
2
zyzy
yyxxyzz
0

Sample Output

1
1
0
1

Program Listing

//Author: Victor Zeng 01/01/2007
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
namespace acm_2003_bombay_decode_problem {

	/*
	test_string return true if with given rules, the teststring is an encoded string of some string
	by applying some of the rules.
	*/
	bool test_string(const vector<string> &rules, string teststring)
	{
		//each pair in the stack contains index into rules, and index into teststring
		stack<pair<size_t,size_t>> partialmatch;
		size_t idx = 0; //current index into teststring
		size_t ridx = 0; //current index into rules
		while (idx<teststring.size())
		{
			//try to match, start with rule at rules[ridx] and substring of teststring from idx
			while(ridx<rules.size()&&rules[ridx].size()>(teststring.size()-idx))
				ridx++;
			if (ridx>=rules.size()) //no match starting from idx
			{	//backtrack
				if (partialmatch.size()==0) //no rule to match from the starting point
					return false;
				ridx = 1+partialmatch.top().first; //try next rule
				idx = partialmatch.top().second; //start from last starting position
				partialmatch.pop();
				continue;
			}
			//try to match rules[ridx] with substring of teststring from idx
			size_t i=0;
			while (i<(rules[ridx]).size() && (rules[ridx])[i]==teststring[i+idx])
				i++;
			if (i==(rules[ridx]).size()) //match found, starting from idx with rules[ridx]
			{
				partialmatch.push(make_pair(ridx, idx));
				idx += (rules[ridx]).size(); //move on
				ridx = 0;
			}
			else //try next rule
				++ridx;
		}
		return true;
	}

	/*
	decode_solver will read in one data set a time which includes n and n lines of substitution rules,
	m and m lines of test strings. Then for each test string, decode_solver will decide if the
	string can be the encoded string for some string by applying the substitution rules. If yes,
	push 1 to the result container, otherwise push 0 to the result container.
	After all input strings have been processed, decode_solver will then print out all results.
	*/
	void decode_solver()
	{
		vector<bool> results; //store results for all test strings
		int i; //var
		string s; //var
		do 
		{
			int n; //number of substitution rules
			cin>>n;
			if (n<=0) //end mark
				break; 
			vector<string> rules;
			for(i=0; i<n; i++)
			{
				cin>>s;
				rules.push_back(s);
			}
			int m; //number of test strings
			cin>>m;
			for (i=0; i<m; i++)
			{
				cin>>s;
				results.push_back(test_string(rules, s));
			}
		} while(1);
		
		for (size_t ite=0; ite!=results.size(); ite++)
			cout<<(results[ite]==true?"1":"0")<<endl;
	}
}