题目链接：http://poj.org/problem?id=1816
思路：建好一颗Trie树，由于给定的模式串可能会重复，在原来定义的结构体中需要增加一个vector用来记录那些以该节点为结尾的字符串的序号，然后就是匹配的过程了，需要注意的是，对于‘？'和'*',每一次都是可以匹配的，并且对于'*'，还得枚举所需要匹配的长度（从0开始）。由于最后的答案可能会有重复，一开始我没有判断时候有重复的，WA了好多次=.=!!.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; const int MAN_N = ( + );
struct Trie {
int index;
Trie *next[];
vector<int > ID; //可能会重复
Trie()
{
index = -;
memset(next, , sizeof(next));
ID.clear();
}
}; Trie *root;
int getID(char ch)
{
if (ch >= 'a' && ch <= 'z') return ch - 'a';
else if (ch == '?') return ;
return ;
}
void Insert(char *str, int pos)
{
int len = strlen(str);
Trie *p = root;
REP(i, , len - ) {
int id = getID(str[i]);
if (p->next[id] == NULL) {
p->next[id] = new Trie();
}
p = p->next[id];
}
p->index = pos;
p->ID.push_back(pos);
}
int N, M;
char str[];
vector<int > ans; void Check(Trie *&p)
{
if (p->next[]) {
if (p->next[]->index != -) {
REP(i, , (int)p->next[]->ID.size()-) ans.push_back(p->next[]->ID[i]);
}
Check(p->next[]);
}
} void dfs(Trie *&p, int pos)
{
if (pos == N) {
if (p->index != -) {
REP(i, , (int)p->ID.size()-) {
ans.push_back(p->ID[i]);
}
}
Check(p);
} else {
if (p->next[getID(str[pos])]) dfs(p->next[getID(str[pos])], pos + );
if (p->next[]) dfs(p->next[], pos + );
if (p->next[]) {
REP(i, pos, N) dfs(p->next[], i);
}
}
} int main()
{
cin >> N >> M;
root = new Trie();
REP(i, , N - ) {
scanf("%s", str);
Insert(str, i);
}
REP(i, , M - ) {
scanf("%s", str);
N = strlen(str);
dfs(root, );
if ((int)ans.size() > ) {
sort(ans.begin(), ans.end());
printf("%d", ans[]);
REP(i, , (int)ans.size()-) {
if (ans[i] != ans[i - ]) printf(" %d", ans[i]);
}
puts("");
} else
puts("Not match");
ans.clear();
}
return ;
}