Trie 字典树
一种很简单的数据结构。
思想
一般在字符串中经常使用。
由于字符集的大小有限可观，我们考虑通过字符之间的迭代构成相连关系。
用处
因为十分基础，在后续的自动机算法中作为前置知识而被广泛理解。
同时，其本身也可以处理一些简单且数据范围较小的题目。
用法
对每一个不同层且不相同的字符进行编号，相同层且字符相同则合并。
那么由此，对于每一个编号不同的字符最多有 个子结点，这里 为字符集大小。
这里给出插入字符串建字典树的代码：
int cnt=0;//cnt表示给字符的编号
void insert(string s)
{
int dep=0,l=s.length();
for(int i=0;i<s;i++)
{
if(!trie[dep][s[i]-'a']) trie[dep][s[i]-'a']=(++cnt);
dep=trie[dep][s[i]-'a'];
}
return;
}
最长公共前缀LCP
把求最长公共前缀放入字典树中去做，不难发现其实就是求两个字符串结尾在字典树上的结点的最近公共祖先。那么，字典树就很巧妙的把 和 联系起来了。
模板题
放一个字典树模板题的链接：洛谷题库-P2580 于是他错误的点名开始了 。