b498.
史蒂芙的單詞統計
內容
背景
史蒂芙手上有本小字典，這字典專門針對某種類型的需求而收集，字典中有非常多特定單詞，為了要辨識語言是否屬於哪一類，判斷方法就是統計一句話中出現多少次字典的單詞，再按照比例數量去偵測。
題目描述
給予 $N$ 個單詞的字典，每個單詞只由大小寫字母和數字構成，接著有 $Q$ 個詢問，每個詢問為一個字串，字串只由大小寫字母和數字構成。對於每個詢問加總每一種單詞出現在字串的個數。
例如經典遊戲《魂斗羅》的秘笈 UUDDLRLRBA，若字典中只有兩個單詞 LR 和 BA，由於 LR 出現 2 次，BA 出現 1 次，統計結果為 1+2 = 3。同理，BANANANA，若字典中只有 ANA 和 BA，則 ANA 出現 3 次，BA 出現一次，統計結果為 3+1 = 4。
這個工作需要極致的效率，就麻煩各位。由於史蒂芙經費有限，只能給予 128MB 的空間。
輸入說明
輸入多組測資。
第一行一個整數 $N$，表示字典中有 $N$ 個單詞，接下來會有 $N$ 行，每一行上只會有一個單詞 $W$。
接著有一個整數 $Q$，表示詢問次數，接下來會有 $Q$ 行，每一行上會有一個字串 $S$。
- $1\le N \le 100000$
- $1 \le Q \le 100000$
- $1 \le |W|, \; |S| \le 100000$
- 字典中單詞總長不超過 $2000000$
輸出說明
對於每個詢問輸出一行一個整數為統計單詞個數。
範例輸入
#1
2 01 01 1 01001 3 LR BA ANA 2 UUDDLRLRBA BANANANA
範例輸出
#1
Case #1: 2 Case #2: 3 4
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (20%): 3.0s , <50M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (10%): 6.0s , <50M
公開 測資點#5 (10%): 8.0s , <50M
公開 測資點#0 (20%): 3.0s , <50M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (10%): 6.0s , <50M
公開 測資點#5 (10%): 8.0s , <50M
提示 ：
節省記憶體為主要目標
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||