a322. 3. 缺字問題

Content

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

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

Input

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

第二行為一個正整數 $L (1 \leq L \leq 8, 1 \leq K^{L} \leq 6 \times 10^{5})$ 。

第三行為小寫英文字串 $S (L \leq | S | \leq 5 \times 10^{5})$ 。

(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$ 。字串 $S$ 為 $accaamcm$ ， $ma$ 為不在 $S$ 內的最小字典序字串。

範測 2:

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

Tags:

出處:

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

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