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

最近更新 : 2024-06-18 18:49

Content

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

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

Input

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

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

第三行為小寫英文字串 $S (L \le |S| \le 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: 

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

範測 2:

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

Tags:
出處:
2024年6月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40907 APCS_Guide (APCS Guide) o078
1156 2024-06-17 14:46
40931 toseanlin@gm ... (Dr. SeanXD) o078
C++詳解-DFS+Map
586 2024-06-19 12:24
40905 a0916933001@ ... (小律) o078
APCS 20240616 題解
629 2024-06-17 13:25
42810 hsuchenru@gm ... (Thinking) o078
set是個好東西
165 2024-10-04 22:25
41975 010521@mail. ... (Terry practice ...) o078 130 2024-09-15 20:59