Trie

Trie

Trie又叫字典树、前缀树。利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

暂且分成处理字符的Trie，和处理二进制的01Trie

字符

remember the word UVALive-3942

struct Node {
	int son[26],val;//son记字符分支，val等记结束点状态
	void init() {//初始化
		memset(son,0,sizeof(son));
		val=0;
	}
};
int cur,dp[N];
struct Trie {
	Node node[N*10];//节点
	int sz;
	void init() {
		sz=0;
		node[0].init();
	}
	void insert(string s) {//插入操作
		int now=0;
		for(int i=0; i<s.size(); i++) {
			int &nxt=node[now].son[s[i]-'a'];
			if(!nxt)node[nxt=++sz].init();//如果找到的点不存在，新开一个点
			now=nxt;
		}
		node[now].val=1;
	}
	void search(string s) {//查找操作
		int now=0;
		for(int i=0; i<s.size(); i++) {
			int & nxt=node[now].son[s[i]-'a'];
			now=nxt;
			if(!nxt)return;
			if(node[now].val==1) {//单词结束的节点
				dp[cur]=(dp[cur]+dp[cur+i+1])%20071027;
			}
		}
	}
} T;