Posted on 2010-12-07 16:34
李东亮 阅读(2176)
评论(1) 编辑 收藏 引用 所属分类:
acm
HDU 1251 统计难题
要看论文准备毕业设计了，好几周都没有搞ACM了，今天实在手痒了，就去hdu上溜达了一圈，挑几个题做，于是乎就看到了这个题，典型的字典树。
题目要求输出以某个字符串为前缀的word的数目，建立字典树之后就是个简单的查询了，为了性能采用了静态字典树，由于不知道会有多少个单词就猜了下感觉10w应该够了吧，提交上去access violation，明显的越界访问，修改为20W一样出错，后来火了，直接开到50w过了，测试数据相当狠呀。
不多说了，参考代码如下。
#include <stdio.h>
#include <stdlib.h>
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;
}