Posted on 2010-12-07 16:34
李東亮 閱讀(2206)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
acm
HDU 1251 統(tǒng)計(jì)難題
要看論文準(zhǔn)備畢業(yè)設(shè)計(jì)了，好幾周都沒(méi)有搞ACM了，今天實(shí)在手癢了，就去hdu上溜達(dá)了一圈，挑幾個(gè)題做，于是乎就看到了這個(gè)題，典型的字典樹(shù)。
題目要求輸出以某個(gè)字符串為前綴的word的數(shù)目，建立字典樹(shù)之后就是個(gè)簡(jiǎn)單的查詢了，為了性能采用了靜態(tài)字典樹(shù)，由于不知道會(huì)有多少個(gè)單詞就猜了下感覺(jué)10w應(yīng)該夠了吧，提交上去access violation，明顯的越界訪問(wèn)，修改為20W一樣出錯(cuò)，后來(lái)火了，直接開(kāi)到50w過(guò)了，測(cè)試數(shù)據(jù)相當(dāng)狠呀。
不多說(shuō)了，參考代碼如下。
#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;
}