a181. 逆逆向思考
Tags : Trie
Accepted rate : 38人/57人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-07-11 23:19

Content

Trie,又稱單詞查找樹鍵樹,是一種樹形結構,是一種哈希樹的變種。典型應用是用於統計和排序大量的字元串(但不僅限於字元串),

所以經常被搜索引擎系統用於文本詞頻統計。它的優點是:最大限度地減少無謂的字元串比較,查詢效率比哈希表高。

以上資料引用自維基百科

現在想請你模擬出一個簡單的 Trie

 

這是一個 Trie 結構的例子:

在這個 Trie 結構中,保存了 A、to、tea、ted、ten、i、in、inn 這 8 個字元串,僅佔用 8 個位元組(不包括指針佔用的空間)。

怕有人因為瀏覽器問題, 排版亂掉

範例輸出 :

 

 
Input

有多筆測試資料,

第一行有一個數字 N, 代表有 N 個字串

每個字串長度不超過 100,0000 個字元長度 

所涵蓋的字元為 ASCII 33 ~ 127 (可顯示字元, 除了空白 32 外)

× 不給 N 的範圍, 是希望你用 linked list 做(用內建 or 動態陣列, 也是OK)

× 不用擔心記憶體的問題(用鏈結做的話)

× 記得用free();

Output

對於每一組測資

將整個 Trie 輸出

按照 ASCII 由小排到大

詳情請參考範例輸出

Sample Input #1
8
A
to
tea
ted
ten
i
in
inn
10
/
/7
/?
/7g
G
(
({
(n
/?J
/)
Sample Output #1

											
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <10M
Hint :
ZeroJudge 的 主機, 果真是進步了, 原本遞迴深度 10 萬就會 stack overflow
每想到現在出到 20 萬, 仍然不會 overflow
所以現在出到遞迴深度 100 萬, 你家的主機, 也差不多 10 萬, 就準備吃 RE 了
那你要怎麼寫呢 ?
Tags:
Trie
出處:
[管理者: morris1028 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」