a322. 3. 缺字問題
Tags :
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2024-10-31 15:46

Content

給定一個大小為 K 個字母的集合和字串 S,求出在使用該集合所組出長度為 L 字串中,不為字串 S 子字串的最小字典序字串為何。

例如字母集合 {a,c,m},其能組出長度為 2 的字串字典序由小到大排序為 aa<ac<am<ca<cc<cm<ma<mc<mm。字串 Saccaamcm,因此 ma 為不在 S 內的最小字典序字串。

Input

第一行為一個長度為 K(1K10) 的小寫字母字串代表字母集合,保證字元不重複且照字元由小到大排序。

第二行為一個正整數 L(1L8,1KL6×105)

第三行為小寫英文字串 S(L|S|5×105)

(20 分): |S|=1000
(80 分): 無限制

Output

輸出滿足題目要求的最小字典序字串

Sample Input #1
acm
2
accaamcm
Sample Output #1
ma
Sample Input #2
dp
3
dddppdpd
Sample Output #2
pdd
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

範測 1: 

字母集合 {a,c,m},其能組出長度為 2 的字串字典序由小到大為 aa<ac<am<ca<cc<cm<ma<mc<mm。字串 Saccaamcmma 為不在 S 內的最小字典序字串。

範測 2:

字母集合 {d,p},其能組出長度為 3 的字串字典序由小到大為 ddd<ddp<dpd<dpp<pdd<pdp<ppd<ppp。字串 Sdddppdpdpdd 為不在 S 內的最小字典序字串。

Tags:
出處:
2024年6月APCS演算法海牛 [管理者: ktlai(測試員) ]


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