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 \leq N \leq 100000$
$1 \leq Q \leq 100000$
$1 \leq | W |, | S | \leq 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

提示：

節省記憶體為主要目標

標籤:

AC 自動機 DA trie

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」