【例3-2】单词查找树

http://ybt.ssoier.cn:8088/problem_show.php?pid=1337

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[100005];
 4 int tot=0;//编号
 5 int trie[100005][26];//字典树
 6 void insert(char *s){//插入单词s
 7     int len=strlen(s);//单词s的长度
 8     int root=0;//字典树上当前匹配到的结点
 9     for(int i=0;i<len;i++){
10         int id=s[i]-'A';//子节点编号
11         if(trie[root][id]==0)//如果之前没有从root到id的前缀 
12             trie[root][id]=++tot;//插入
13         root=trie[root][id];//顺着字典树往下走
14     }
15 }
16 int main(){
17     while(scanf("%s",s)!=EOF)
18         insert(s);
19     printf("%d
", tot + 1);
20     return 0;
21 }