Posted on 2010-12-07 16:34
李東亮 閱讀(2193)
評論(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;
}