题目链接：hdu1305

题目大意：给一大堆01串，并以9表示一组01串输入结束，问这些串之间是否至少有一个串是另一个串的前缀。

解题思路：毫无疑问，可以用Trie来维护这些串，每次插入时判断是否含有当前串str的前缀串或者自己是别的串的前缀串，代码种的查询时query2。查询的复杂度O(n)。

字典树介绍

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

-- 摘自百度百科

核心思想

利用空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

三个基本性质：

  1. 根结点不包含字符，除根结点外每一个结点都只包含一个字符。

  2. 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。

  3. 每个结点的所有子结点包含的字符都不相同。

主要操作

增加(insert/add)，删(delete)，查(query/find)

实现

分别由动态Trie和静态Trie两种方法

AC代码(根据原理自己YY的，不要参考此写法)：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>

using namespace std;
#define N 2

char str[10005];

struct Trie {
	bool ishave;
	int num;
	Trie* nxt[N]; //Trie指针表

	Trie() {
		for (int i = 0; i < N; i++) {
			nxt[i] = NULL;
		}
		num = 0;
		ishave = false;
	}

	~Trie() {
		for (int i = 0; i < N; i++) {
			if(nxt[i] != NULL) {
				delete nxt[i];
			}
		}
	}

};

Trie* root;

void _insert (char str[]) {
	int len = strlen(str);
	char tmp;
	Trie* qtmp = root;

	for (int i = 0; i < len; i++) {
		tmp = str[i] - '0';
		if(qtmp->nxt[tmp] == NULL) {
			qtmp->nxt[tmp] = new Trie();
		}
		qtmp = qtmp->nxt[tmp];
		qtmp->num++; //以当前前缀的单词数+1
	}
	qtmp->ishave = true;
	return ;
}

void _delete (char str[]) {
	int len = strlen(str);
	char tmp;
	Trie* qtmp = root;

	for (int i = 0; i < len; i++) {
		tmp = str[i] - '0';
		if(qtmp->nxt[tmp] == NULL) {
			return ;  //没有该单词
		}
		qtmp = qtmp->nxt[tmp];
		qtmp->num--;
	}
	delete qtmp;
}

bool _query (char str[]) {
	int len = strlen(str);
	char tmp;
	Trie* qtmp = root;

	for (int i = 0; i < len; i++) {
		tmp = str[i] - '0';
		if(qtmp->nxt[tmp] == NULL) {
			return false;
		}
		qtmp = qtmp->nxt[tmp];
	}
	return true;
}

void _delete_all (Trie* father) {
	for (int i = 0; i < N; i++) {
		if(father->nxt[i] != NULL) {
			_delete_all(father->nxt[i]);
			father->nxt[i] = NULL;
		}
	}
	delete father;
}

void Init () {
	if(root)
		_delete_all(root);
	root = new Trie();
}

bool _query2 (char str[]) {  //查询是否存在str前缀
	int len = strlen(str);
	char tmp;
	Trie* qtmp = root;

	for (int i = 0; i < len; i++) {
		tmp = str[i] - '0';
		if(qtmp->nxt[tmp] == NULL) {
			return false;
		}
		if(qtmp->nxt[tmp]->ishave == true) {
			return true;
		}
		qtmp = qtmp->nxt[tmp];
	}
	return true;
}

int main() {
	int cnt = 1;
	bool flag = false;
	root = new Trie();
	while (~scanf("%s",str)) {
		if(strcmp(str,"9") == 0) {
			if(flag) {
				printf("Set %d is not immediately decodable\n",cnt++);
			}else {
				printf("Set %d is immediately decodable\n",cnt++);
			}
			flag = false;
			Init();
			continue;
		}
		if(!flag && _query2(str)) {
			flag = true;
		}
		_insert(str);
	}
	return 0;
}