【题目描述】
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：
1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；
2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；
3．在满足上述条件下，该单词查找树的结点数最少。
4．例如图3-2左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。
【输入】
为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。
【输出】
仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。
【输入样例】
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC【输出样例】
13
#include <bits/stdc++.h>
using namespace std;
struct Node
{
char data;
int child [26];
};
Node tree[34000];
int root=1,cnt=1; //根结点为1,cnt为当前分配到的一维数组元素的个数
void Insert(string s)
{
int point=root; //要注意根为空，没有存任何节点，但需要分配内存，即节点下标为1。然后别的节点依次从2开始
for(int i=0;i<s.size();i++)
{
int foundChild=s[i]-'A';
if( tree[ point ].child [ foundChild ]==0 ) //没有该结点
{
cnt++; //分配新结点
tree[ point ].data=s[i];
tree[ point ].child[ foundChild ]=cnt;
point=tree[ point ].child [ foundChild ]; //加完后要继续进行字结点,否则下次加字符不是在此下点加
}
else
point=tree[ point ].child [ foundChild ];
}
}
int main()
{
string s;
while(cin>>s)
Insert(s);
cout<<cnt;
return 0;
}
标签：结点,信奥,int,1337,列表,单词,查找,通题,对应 From： https://www.cnblogs.com/nanshaquxinaosai/p/18419029