本文主要是介绍Trie树入门：HDU 1251，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题搞了几个小时，从昨天看题目然后从刘汝佳那本训练指导中看了Trie树的插入模板，然后就想这题怎么查找，然后今早竟然做了卡了好久，因为书中是给二维数组的，而这题无限输入啊，直到文件结束，我就在想用vector代替数组，但是实行起来出错了。然后又用map代替，样例对了，可是提交还是错了。然后又换成二维数组，上线从4000000一直提交直降到400000才没有内存超出，可是还是wrong了，再在没有内存超出，说明这二维数组上线400000已经够了，应该是代码问题了。可是也没有发现哪里错啊。唉……提交多次都是wrong，无语了。后面看了一下输入输出，唉……然后改成gets就对了，尼玛真无语……从头搞到尾，原来是输入输出问题……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define INF 510010
#define maxn 400010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int ch[maxn][27]; //节点编号
int sz; //字典树的节点个数
int val[maxn]; //节点的值，为1说明新增一个字符串
void init() //初始化
{sz=1;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));
}
int idx(char c)
{return c-'a';
}
void insert(char *s)
{int u=0,i,c,l=strlen(s);for(i=0; i<l; i++){c=idx(s[i]);if(!ch[u][c]) ch[u][c]=sz++;u=ch[u][c];val[u]++;}
}
int query(char *s)
{int u=0,i,c,l=strlen(s);for(i=0; i<l; i++){c=idx(s[i]);if(!ch[u][c]) return 0;u=ch[u][c];}return val[u];
}
int main()
{char s[12];init();while(gets(s),s[0]!='\0')insert(s);while(gets(s))printf("%d\n",query(s));
}
这篇关于Trie树入门：HDU 1251的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
