poj 1816 Wild Words(辞書ツリー＋dfs)

3410 ワード
データ構造-Trie 検索
この問題は辞書の木を作って検索しますか?それとも簡単に思いつきますか?と＊は特別扱いで、主に＊はうまく処理されていません.
何故なら?人の気持ちを表す文字ができますが、＊は一列です.
実は＊が存在すると判断する度に、＊の中で文字列の長さを列挙すればいいです.
/*****************************************
Author      :Crazy_AC(JamesQi)
Time        :2016
File Name   :
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node {
	vector vec;
	node* nxt[30];
	node() {
		vec.clear();
		for (int i = 0;i < 30;++i)
			nxt[i] = NULL;
	}
}*root;
inline int getid(char c) {
	if (c == '?') return 26;
	if (c == '*') return 27;
	return c - 'a';//[0, 25]
}
void insert(char *s, int num) {
	int len = strlen(s);
	node* p = root;
	for (int i = 0;i < len;++i) {
		int id = getid(s[i]);
		if (p->nxt[id] == NULL) p->nxt[id] = new node();
		p = p->nxt[id];
	}
	p->vec.push_back(num);
}
vector vec;
bool vis[100010];
void dfs(char* s,node* p) {
	if (s[0] == '\0') {
		if (p->vec.size() != 0) {
			int size = p->vec.size();
			for (int i = 0;i < size;++i) {
				int num = p->vec[i];
				if (!vis[num]) {
					vis[num] = true;
					vec.push_back(num);
				}
			}
		}
		while(p->nxt[27] != NULL) {
			if (p->nxt[27]->vec.size() != 0) {
				int size = p->nxt[27]->vec.size();
				for (int i = 0;i < size;++i) {
					int num = p->nxt[27]->vec[i];
					if (!vis[num]) {
						vis[num] = true;
						vec.push_back(num);
					}
				}
			}
			p = p->nxt[27];
		}
		return ;
	}
	int id = getid(s[0]);
	if (p->nxt[26] != NULL) dfs(s + 1, p->nxt[26]);
	if (p->nxt[id] != NULL) dfs(s + 1, p->nxt[id]);
	if (p->nxt[27] != NULL) {
		// if (p->nxt[27]->nxt[27] != NULL) dfs(s, p->nxt[27]);//907ms
		int i;
		for (i = 0;s[i];i++) {//           
			//              i,             i + 1
			id = getid(s[i]);
			if (p->nxt[27]->nxt[id] != NULL) dfs(s + i + 1, p->nxt[27]->nxt[id]);
			if (p->nxt[27]->nxt[26] != NULL) dfs(s + i + 1, p->nxt[27]->nxt[26]);
		}
		if (p->nxt[27]->nxt[27] != NULL) dfs(s, p->nxt[27]);//860ms
		dfs(s + i, p->nxt[27]);//        
	}
}
void del(node* p) {
	for (int i = 0;i < 30;++i)
		if (p->nxt[i] != NULL) del(p->nxt[i]);
	delete p;
}
int main()
{	
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	int n, m;
	char s[40];
	while(~scanf("%d%d",&n,&m)) {
		root = new node();
		for (int i = 0;i < n;++i) {
			scanf("%s",s);
			insert(s, i);
		}
		for (int i = 0;i < m;++i) {
			scanf("%s", s);
			memset(vis, false,sizeof vis);
			vec.clear();
			dfs(s, root);
			if (vec.size() == 0) puts("Not match");
			else {
				sort(vec.begin(), vec.end());
				int len = vec.size();
				for (int j = 0;j < len;++j)
					printf("%d%c", vec[j], j == len - 1?'
':' ');
			}
		}
		del(root);
	}
	return 0;
}
中国大学MOOC-陳越、何欽銘-データ構造-2018秋07-図4ハリー・ポッターの試験(25点)