b498. 史蒂芙的單詞統計
標籤 : AC 自動機 DA trie
通過比率 : 9人/18人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-23 08:10

內容

背景

史蒂芙手上有本小字典,這字典專門針對某種類型的需求而收集,字典中有非常多特定單詞,為了要辨識語言是否屬於哪一類,判斷方法就是統計一句話中出現多少次字典的單詞,再按照比例數量去偵測。

題目描述

給予 $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
提示 :

節省記憶體為主要目標

標籤:
AC 自動機 DA trie
出處:
[管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

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