HDU上的ACM字典树参考代码
- 时间：2015年04月02日 15:40:00 来源：魔法猪系统重装大师官网 人气：18318
要看论文准备毕业设计了，好几周都没有搞ACM了，今天实在手痒了，就去hdu上溜达了一圈，挑几个题做，于是乎就看到了这个题，典型的字典树。
题目要求输出以某个字符串为前缀的word的数目，建立字典树之后就是个简单的查询了，为了性能采用了静态字典树，由于不知道会有多少个单词就猜了下感觉10w应该够了吧，提交上去access violation，明显的越界访问，修改为20W一样出错，后来火了，直接开到50w过了，测试数据相当狠呀。
不多说了，参考代码如下。
#include
#include
struct node
{
int cnt;
int childs[26];
};
int avail = 1;
int cur = 0;
struct node tree[500000];
char buf[15];
int main(void)
{
int i;
int root;
int index;
int flag;
/*freopen("in.txt", "r", stdin);*/
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
while (buf[i] != '\n')
{
index = buf[i]-'a';
if (tree[root].childs[index] == 0)
{
tree[root].childs[index] = avail++;
}
++tree[tree[root].childs[index]].cnt;
root = tree[root].childs[index];
++i;
}
}
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
flag = 1;
while (buf[i] != '\n')
{
index = buf[i] - 'a';
if (tree[root].childs[index] == 0)
{
flag = 0;
break;
}
root = tree[root].childs[index];
++i;
}
printf("%d\n", flag == 1 ? tree[root].cnt : 0);
}
return 0;
}
HDU,上的,ACM,字典,树,参考,代码,要看,论文,
题目要求输出以某个字符串为前缀的word的数目，建立字典树之后就是个简单的查询了，为了性能采用了静态字典树，由于不知道会有多少个单词就猜了下感觉10w应该够了吧，提交上去access violation，明显的越界访问，修改为20W一样出错，后来火了，直接开到50w过了，测试数据相当狠呀。
不多说了，参考代码如下。
#include
#include
struct node
{
int cnt;
int childs[26];
};
int avail = 1;
int cur = 0;
struct node tree[500000];
char buf[15];
int main(void)
{
int i;
int root;
int index;
int flag;
/*freopen("in.txt", "r", stdin);*/
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
while (buf[i] != '\n')
{
index = buf[i]-'a';
if (tree[root].childs[index] == 0)
{
tree[root].childs[index] = avail++;
}
++tree[tree[root].childs[index]].cnt;
root = tree[root].childs[index];
++i;
}
}
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
flag = 1;
while (buf[i] != '\n')
{
index = buf[i] - 'a';
if (tree[root].childs[index] == 0)
{
flag = 0;
break;
}
root = tree[root].childs[index];
++i;
}
printf("%d\n", flag == 1 ? tree[root].cnt : 0);
}
return 0;
}
上一篇：多线程游戏服务器技术开发
下一篇：企业级大数据量分页控件
