# APCS實作題2024年6月第3題：缺字問題

> 日期：2024年7月4日
> 作者：王一哲
> 題目來源：2024年6月實作題第3題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o078)

## 題目

### 問題描述

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

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

### 輸入說明

第一行為一個長度為 $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%：無限制。
<br />

### 輸出格式

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

<br />

### 範例輸入1

acm
2
accaamcm

### 範例輸出1

ma

### 範例輸入2

dp
3
dddppdpd

### 範例輸出2

pdd

<br />

## Python 程式碼

### 寫法1

依照字典順序枚舉C能組成的子字串s，再用 in 檢查 s 是否於 S 之中。最後一筆測資會超時。

C = input()  # 字母集合字串
L = int(input())  # 目標子字串長度
S = input()  # 要找子字串的S
K = len(C)  # C的長度
idx = [0]*L  # 組成子字串s時，由C取字母的索引值

for _ in range(K**L):  # 最多執行 K**L 次
    s = "".join([C[i] for i in idx])  # 由C取出字母組成字串s
    if s not in S:  # 如果s不在S之中，找到答案了
        print(s)  # 印出s
        break  # 中止 for 迴圈
    # 更新 idx，先將最後一位加1，再檢查是否需要進位，如果不需要進位就中止 for 迴圈
    idx[-1] += 1
    for k in range(1, L):
        if idx[L-k] == K:
            idx[L-k] -= K
            idx[L-k-1] += 1
        else: break

<br /><br />

### 寫法2

程式運作邏輯與寫法1相同，但是先枚舉S所有的子字串存入集合 sub，再檢查C組成的子字串s是否已於 sub 之中，執行速度較快。費時最久約為 0.6 s，使用記憶體最多約為 17 MB，通過測試。

C = input()  # 字母集合字串
L = int(input())  # 目標子字串長度
S = input()  # 要找子字串的S
K = len(C)  # C的長度
N = len(S)  # S的長度
idx = [0]*L  # 組成子字串s時，由C取字母的索引值
sub = set()  # S所有的子字串集合

# 掃過S，將所有的子字串加入 sub
for i in range(N-L+1): sub.add(S[i:i+L])

for _ in range(K**L):  # 最多執行 K**L 次
    s = "".join([C[i] for i in idx])  # 由C取出字母組成字串s
    if s not in sub:  # 如果s不在sub之中，找到答案了
        print(s)  # 印出s
        break  # 中止 for 迴圈
    # 更新 idx，先將最後一位加1，再檢查是否需要進位，如果不需要進位就中止 for 迴圈
    idx[-1] += 1
    for k in range(1, L):
        if idx[L-k] == K:
            idx[L-k] -= K
            idx[L-k-1] += 1
        else: break

<br /><br />

## C++ 程式碼

### 寫法1

依照字典順序枚舉C能組成的子字串s，再用 find 檢查 s 是否於 S 之中。最後一筆測資會超時。

#include <iostream>
#include <cstring>  // for memset
//#include <vector>
#include <string>
#include <cmath>  // for pow
using namespace std;

int main() {
    string C, S;  // 字母集合字串C，要找子字串的S
    unsigned int L, K, N;  // 目標子字串長度L，C的長度K，S的長度N
    cin >> C >> L >> S;  // 讀取 C、L、S
    K = C.size(); N = S.size();  // 取得C、S的長度
    unsigned int idx[L];  // 組成子字串s時，由C取字母的索引值
    memset(idx, 0, sizeof(idx[0])*L);  // 先全部設定為0
    //vector<unsigned int> idx (L, 0);  // 可以改用 vector，取代以上2行
    /* 主要的解題過程，最多執行 K**L 次 */
    for(unsigned int i=0; i<(unsigned int)pow(K, L); i++) {
        // 由C取出字母組成字串s
        string s = "";
        for(unsigned int j=0; j<L; j++) s += C[idx[j]];
        // 如果s不在S之中，找到答案了，印出s，中止 for 迴圈
        if (S.find(s) > N) {
            cout << s << "\n";
            break;
        }
        // 更新 idx，先將最後一位加1，再檢查是否需要進位，如果不需要進位就中止 for 迴圈
        idx[L-1]++;
        for(unsigned int k=1; k<L; k++) {
            if (idx[L-k] == K) {
                idx[L-k] -= K;
                idx[L-k-1]++;
            } else {
                break;
            }
        }
    }
    return 0;
}

<br /><br />

### 寫法2

程式運作邏輯與寫法1相同，但是先枚舉S所有的子字串存入集合 sub，再檢查C組成的子字串s是否已於 sub 之中，執行速度較快。費時最久約為 0.3 s，使用記憶體最多約為 9.2 MB，通過測試。

#include <iostream>
#include <cstring>  // for memset
#include <string>
#include <cmath>  // for pow
#include <set>
using namespace std;

int main() {
    string C, S;  // 字母集合字串C，要找子字串的S
    unsigned int L, K, N;  // 目標子字串長度L，C的長度K，S的長度N
    cin >> C >> L >> S;  // 讀取 C、L、S
    K = C.size(); N = S.size();  // 取得C、S的長度
    unsigned int idx[L];  // 組成子字串s時，由C取字母的索引值
    memset(idx, 0, sizeof(idx[0])*L);  // 先全部設定為0
    set<string> sub;
    for(unsigned int i=0; i<=N-L; i++) sub.insert(S.substr(i, L));
    /* 主要的解題過程，最多執行 K**L 次 */
    for(unsigned int i=0; i<(unsigned int)pow(K, L); i++) {
        // 由C取出字母組成字串s
        string s = "";
        for(unsigned int j=0; j<L; j++) s += C[idx[j]];
        // 如果s不在sub之中，找到答案了，印出s，中止 for 迴圈
        if (sub.count(s) == 0) {
            cout << s << "\n";
            break;
        }
        // 更新 idx，先將最後一位加1，再檢查是否需要進位，如果不需要進位就中止 for 迴圈
        idx[L-1]++;
        for(unsigned int k=1; k<L; k++) {
            if (idx[L-k] == K) {
                idx[L-k] -= K;
                idx[L-k-1]++;
            } else {
                break;
            }
        }
    }
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`