POJ1816(사전 트리 모호 일치)

모호한 일치이기 때문에 dfs로 모든 상황을 열거해야 합니다
갱점1: 중복 모드 있음
2: 문자열 일치 후에도 * 기호가 있을 수 있음
예제:
            6 1
            t
            t
            t*
            t*
            t**
            t***
출력: 0 1 2 3 4 5
코드:

#include 
#include  
#include 
#include 

using namespace std;
const int maxn = 100005;
int trie[maxn][28];
int val[maxn];
int ans[maxn];
int n, m, tot, anscnt;
vector  G[maxn];

int ID(char ch)
{
	if (ch == '*') return 26;
	if (ch == '?') return 27;
	
	return ch-'a';
}

void insert(char str[],int cnt)
{
	int u = 0, id;
	int len = strlen(str);
	for (int i = 0; i < len; i++)
	{
		id = ID(str[i]);
		if (!trie[u][id])
			trie[u][id] = tot++;
		u = trie[u][id];
	}
	val[u] = cnt;
	G[u].push_back(cnt);
}

void query(char word[],int u,int pos,int k)
{
	
	int id = 26;
	if (trie[u][id])//"*"            ，               *** 
	for (int i = pos; i <= k; i++)
		query(word,trie[u][id],i,k);
	if (pos == k && G[u].size() != 0)
	{
		int len = G[u].size();
		for (int i = 0; i < len; i++)
			ans[anscnt++] = G[u][i]-1;
		return;
	}
	id = ID(word[pos]);
	if (trie[u][id])
		query(word,trie[u][id],pos+1,k);	
	
	id = 27;
	if (trie[u][id])
		query(word,trie[u][id],pos+1,k);
}

void init()
{
	memset(val,0,sizeof(val));
	memset(trie,0,sizeof(trie));
	for (int i = 0; i < maxn; i++)
		G[i].clear();
	tot = 1;
}

int main()
{
	char str[25];
	while (scanf("%d%d",&n,&m) != EOF)
	{
		init();
		for (int i = 0; i < n; i++)
		{
			scanf("%s",str);
			insert(str,i+1);
		}
		while (m--)
		{
			anscnt = 0;
			scanf("%s",str);
			int len = strlen(str);
			query(str,0,0,len);
			if (anscnt == 0)
			{
				puts("Not match");
				continue;
			}
			sort(ans,ans+anscnt);
			for (int i = 0; i < anscnt; i++)
			{
				if (i != 0 && ans[i] == ans[i-1]) continue;
				printf("%d ",ans[i]);
			}
			puts("");
		}
	}
	
	return 0;
}