【oiClass 1502】查单词（Trie字典树）
题目描述
全国英语四级考试就这样如期来了，可是小y依然没有做好充分准备。为了能够大学毕业，可怜的小y决定作弊。小y费尽心机，在考试的时候夹带了一本字典进考场，但是现在的问题是，考试的时候可能有很多的单词要查，小y能不能来得及呢？
输入
第一行一个整数N，表示字典中一共有多少个单词（N<=10000）。接下来每两行表示一个单词，其中：
第一行是一个长度<=100的字符串，表示这个单词，全部小写字母，单词不会重复。
第二行是一个整数，表示这个单词在字典中的页码。
接下来是一个整数M，表示要查的单词数(M<=10000)。
接下来M行，每行一个字符串，表示要查的单词，保证在字典中存在。
输出
M行，每行一个整数，表示第I个单词在字典中的页数。Trie字典树模板题，把每个单词的页数存在单词在trie里最后一个字母的位置即可。
1 #include <cstring> 2 #include <cstdio> 3 4 int n,m,x,cnt; 5 char s[100]; 6 7 struct node{ 8 int val,son[26]; 9 }trie[1000001]; 10 11 void insert(char s[],int k){ 12 int len=strlen(s),x=0; 13 for(int i=0;i<len;++i){ 14 int v=s[i]-'a'; 15 if(!trie[x].son[v]) 16 trie[x].son[v]=++cnt; 17 x=trie[x].son[v]; 18 } 19 trie[x].val=k; 20 } 21 22 int query(char s[]){ 23 int len=strlen(s),x=0; 24 for(int i=0;i<len;++i){ 25 int v=s[i]-'a'; 26 x=trie[x].son[v]; 27 } 28 return trie[x].val; 29 } 30 31 int main(void){ 32 scanf("%d",&n); 33 for(int i=1;i<=n;++i){ 34 scanf("%s%d",&s,&x); 35 insert(s,x); 36 } 37 scanf("%d",&m); 38 for(int i=1;i<=m;++i){ 39 scanf("%s",&s); 40 printf("%d\n",query(s)); 41 } 42 }优质内容筛选与推荐>>
1、disabled与tap(input的disabled='disabled'时tap事件任可触发)
2、在esri-ajax环境中涮新asp.net显示控件的通用方法
3、Word Ladder II
4、关于安卓开发当中通过java自带的HttpURLConnection访问XML的java.io.EOFException问题
5、.Net Core 2.*+ InfluxDB+Grafana+App Metrics实时性能监控