POJ-1816 Wild Words(ぼかした状態では辞書のツリーにマッチ)

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 many word patterns and some wods in your hand.For each word,your task is to tell which patterns match.
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 works.Each of the following nling N lineas the patternars,patternars.each of the last M lineas contains a word.You can assiume that the length of patterns will not exced 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

            簡単に言えば、辞書の木でdfsを行います.ここで注意しているのは、最後に答えを保存する時にセットを使うとtleができます.

#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e6 + 5;
int nex[N][30];
int tot = 0; vectorG[N];
int Hash(char x) {
	if (x == '?')
		return 26;
	if (x == '*')
		return 27;
	return  x - 'a';
}
void insert(string m, int id) {
	int len = m.length();
	int root = 0;
	for (int i = 0; i < len; i++) {
		int id = Hash(m[i]);
		if (nex[root][id] == 0)
			nex[root][id] = ++tot;
		root = nex[root][id];
	}
	G[root].push_back(id);
}
vectorans;
void dfs(string m, int pos, int root) {
	if (pos == m.length()) {
		if (nex[root][27] != 0) {
			for (int i = pos; i <= m.length(); i++) {
				dfs(m, i, nex[root][27]);
			}
		}
		for (int i = 0; i < G[root].size(); i++) {
			ans.push_back(G[root][i]);
		}
		return;
	}
	if (nex[root][Hash(m[pos])] != 0) {
		dfs(m, pos + 1, nex[root][Hash(m[pos])]);
	}
	if (nex[root][26] != 0) {
		dfs(m, pos + 1, nex[root][26]);
	}
	if (nex[root][27] != 0) {
		for (int i = pos; i <= m.length(); i++) {
			dfs(m, i, nex[root][27]);
		}
	}
}
void finstr(string m) {
	ans.clear();
	dfs(m, 0, 0);
	if (ans.size() == 0) {
		cout << "Not match
";
		return;
	}
	sort(ans.begin(), ans.end()); int sum = 0;
	for (int i = 0; i < ans.size(); i++) {
		if (i == 0 || ans[i] != ans[i - 1]) {
			if (sum != 0)cout << " ";
			cout << ans[i];
			sum++;
		}
	}
	cout << "
";
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string t; cin >> t;
		insert(t, i - 1);
	}
	for (int i = 0; i < m; i++) {
		string t; cin >> t;
		finstr(t);
	}
	return 0;
}