POJ-1816 Wild Words(辞書のツリーの問題)

Wildワールド
Time Limit: 2000 MS
 
メモリLimit: 65536 KB
 
64 bit IO Format: %I 64 d&%I 64 u
Submit Status
Description
Aワードis a string of lowercases.Aワードpattern is a string of lowercases、'?s and'*'s.In a pattern,a'?matches any single lowercase,and a'*'matches none or more lowercases.
 
The re are many word patterns and some wods in your hand.For each word,your task is to tell which patterns match it.
 
Input
The first line of input contains two integers N(0＜N==100000)and M(0＜M==100)、representing the number of word patterns and the number of word works.Each of the following nling＿N lineas＿the＿the patternars,lines.
 
You can assiume that the length of patterns will not exceed 6、and the length of wors will not exceed 20.
 
Output
For each word,print a line contains the numbers of matched patterns by increasung order.Each number is follo wed by a single blank.If there isのpattern can match the word,print“Not match”.
Sample Input

5 4
t*
?h*s
??e*
*s
?*e
this
the
an
is

Sample Output

0 1 3 
0 2 4 
Not match
3

#include
#include
#include
#include
#define MAXN 100010
using namespace std;

int n, m;
struct Trie
{
	int i;
	Trie *a[28];
	Trie()
	{
		for (i = 0; i<28; i++)
			a[i] = NULL;        //     ，        
		i = -1;                 //   “  ”     -1  
	}
};

Trie root;
char p[7], s[22];
int set[MAXN];
bool mat[MAXN];

void Insert(Trie *rt, int k, int j)        //                    ， set[k]，k         ，set[k]            
{                                          //              。
	int i, t;
	if (p[j] == '\0')                      //i            ，   。
	{
		if (rt->i>-1)
			set[k] = set[rt->i];            //set【k】      ，   。            ，      i。
		else
			rt->i = k;                      //  
		return;
	}
	if (p[j] == '*')
		t = 27;
	else if (p[j] == '?')
		t = 26;
	else
		t = p[j] - 'a';        //0 27   a z ？、*
	if (!rt->a[t])
	{
		rt->a[t] = new Trie;
	}
	Insert(rt->a[t], k, j + 1);
}

void Query(Trie *rt, int j)              //dfs
{
	if (rt->a[27] && rt->a[27]->i>-1)    //      *，      ，  
		mat[rt->a[27]->i] = true;
	if (s[j] == '\0')
	{
		if (rt->i>-1)
			mat[rt->i] = true;
		return;
	}
	if (rt->a[s[j] - 'a'])
		Query(rt->a[s[j] - 'a'], j + 1);
	if (rt->a[26])
		Query(rt->a[26], j + 1);
	if (rt->a[27])
	for (int i = j; s[i] != '\0'; i++)   //*         
		Query(rt->a[27], i);
}

int main()
{
	int i, j, k;
	scanf("%d%d", &n, &m);
	root.i = -1;
	for (i = 0; i<28; i++)
		root.a[i] = NULL;
	for (i = 0; i