【题目描述】
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：
1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；
2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；
3．在满足上述条件下，该单词查找树的结点数最少。
4．例如图3-2左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。
【输入】
为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。
【输出】
仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。
【输入样例】
A AN ASP AS ASC ASCII BAS BASIC【输出样例】
131. 关于那个“文件总长度 32K”
题目给的限制很有意思：
单词长度不超过 63。
文件总长度不超过 32K。
第一眼看到 63，下意识觉得“这题很小”，随手开了个 tre[2000]。结果仔细一算不对劲：
32K 是多少？
在C++里，一个char就是 1 字节。
32K=32*1024=32768字节。
这意味着最坏情况下（比如所有单词都长得不一样），这棵树得存 3 万多个字符。
如果要建树，数组至少得开到 40000+ 才稳。
要是按 2000 开，读到第 2001 个字符的时候程序直接就炸了（越界）。
教训：以后看到 32K、64M 这种单位，第一反应必须是换算成字节数。
2. 为什么用 vector 存 Trie？
通常 Trie 树节点是这样写的：
struct node { char data; node* next[26]; // 或者 int next[26] };这样写查找快，但如果节点很多且分叉少，空间浪费严重。
改用vector邻接表写法：
struct node { char data; vector<int> son; // 只存存在的儿子下标 } tre[50000]; // 数组一定要开够！虽然查找时要遍历son数组（多一个 for 循环），但省内存，而且代码写起来其实就是个 DFS，很符合直觉。
3. 最终代码
逻辑很简单：
拿着字符串当前字符
a[k2]去当前节点k1的son列表里找。找到了 -> 递归下一层。
找不到 ->
push_back一个新节点，把ind传进去继续递归。
#include <bits/stdc++.h> #include <vector> using namespace std; struct node{ char data;//记录该结点是哪个字母 vector<int> son;//存放该结点的儿子在树中的下标 }tre[50000];//要开大一点，题目中说文件总长度不超过32K，32k=三万多字节，所以开五万 int cnt;//节点个数 string a; //让tre[1]存放root int len; int ind=1;//现在已经添加了ind个节点，初始为1，因为根节点为root，不包含任何字母 void dfs(int k1,int k2){//现在遍历到树第k1个节点，字符串遍历到第k2个位置 if(k2==len) return; bool flag=0; for(int i=0;i<tre[k1].son.size();i++){//遍历该节点所有孩子，如果和字符串该位置的字母有对应，就去找下一个对应 if(tre[tre[k1].son[i]].data==a[k2]){//如果对应上了，就进入下一轮遍历 dfs(tre[k1].son[i],k2+1); flag=1; break;//对应上了就不需要再找了，退出此轮循环 } } if(flag==0){//目前没有能匹配上的 tre[++ind].data=a[k2];//把a[k2]创建一个新节点，然后储存起来 tre[k1].son.push_back(ind);//把a[k2]节点存进父节点的孩子里，就是拼接上去 dfs(ind,k2+1); } } int main(){ while(cin>>a){ len=a.size();//字符串长度 //建树 //长度不超过63个字母 即每次读进来的单词最多63个字符 dfs深度最多63层 dfs(1,0);//从树的第1个节点开始遍历，从a字符串的a[0]开始遍历 } cout<<ind; }4. 总结
空间换算：
char是 1 字节，题目给多少 K 就乘多少 1024，数组宁大勿小。Vector 写法：用
vector代替定长数组写 Trie 是完全可行的，特别适合不想算next[26]或者字符集不只是 26 个字母的情况。下标坑：
vector存的是下标，取数据时记得套两层tre[tre[k1].son[i]]，这里最容易晕。
