缺字問題 題解｜APCS 2024 年 6 月中高級 第 3 題

前置知識

這題的核心（候選字串照字典序一個一個生出來、第一個沒出現的就是答案）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

• 用遞迴枚舉所有組合：NTUCPC Guide〈枚舉〉與〈遞迴〉——要帶走的是「一位一位決定，每一位都從小的選項試起，填滿了就檢查」；吳邦一《AP325》第 1 章「以遞迴來進行窮舉」的例題 P-1-7 子集合乘積、P-1-9 N-Queen 是同一套寫法（教材 PDF 第 38～43 頁；Python 版第 1 章）。
• set：NTUCPC Guide〈Set 與 Map〉——要帶走的是「放進去、查有沒有，各 \(O(\log n)\)」；《AP325》第 2 章「C++ 可供搜尋的容器（set／map）」一節（教材 PDF 第 57～61 頁；Python 版第 2 章）。
• string 的 substr、find，以及字典序。
• \(K\) 進位（只有最後的「另一種做法」會用到）。

簡潔題意

給字母表 \(A\)（已排序、不重複，最多 \(10\) 個小寫字母）、長度 \(L \le 8\)、字串 \(S\)（長度 \(\le 5 \times 10^5\)，可能含有 \(A\) 以外的字母）。從 \(A\) 挑字母（可以重複）組成長度恰為 \(L\) 的字串，找出「沒有在 \(S\) 中連續出現」的字典序最小者；題目保證存在，而且 \(|A|^L \le 600000\)。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(|S| = 1000\)。
• 子題組 2（\(80\) 分）：無額外限制。

候選字串照字典序生出來，第一個沒出現的就是答案

「字典序最小的缺字」最直接的找法：把所有候選字串照字典序一個一個生出來，每生一個就檢查它有沒有在 \(S\) 裡出現，碰到第一個沒出現的就印出來、停。

照字典序生的方法是遞迴：先決定第 1 個字母、再決定第 2 個……每一位都從 \(A\) 裡最小的字母試起（\(A\) 已經排好序，照順序跑 for (char ch : A) 就是由小到大），填滿 \(L\) 位就檢查。這樣生出來的順序正是字典序：第 1 個字母小的一定先出現，第 1 個字母相同時第 2 個字母小的先出現，以此類推（圖 1）。

會不會把 \(|A|^L\) 個候選全看完？不會：\(S\) 最多只有 \(|S| - L + 1\) 個長度 \(L\) 的視窗，所以最晚檢查到第 \(|S| - L + 2\) 個候選一定會碰到沒出現的。要花多少時間，取決於「檢查一個候選有沒有出現」怎麼做。

先拿下 20 分：直接在 \(S\) 裡找

檢查最直接的寫法：S.find(current)，在 \(S\) 裡從頭找這個子字串。

#include <bits/stdc++.h>
using namespace std;

string A, S;
int L;
string current;                   // 正在組的候選字串

bool search() {                   // 依字典序逐一試候選字串，找到第一個沒出現的就印出來
    if ((int)current.size() == L) {
        if (S.find(current) == string::npos) {     // S 裡找不到：就是它
            cout << current << endl;
            return true;
        }
        return false;
    }
    for (char ch : A) {           // A 已經排好序：先試小的字母
        current.push_back(ch);
        if (search()) return true;
        current.pop_back();
    }
    return false;
}

int main() {
    cin >> A >> L >> S;
    search();
    return 0;
}

每次 find 最多要掃過整個 \(S\)，最多檢查 \(|S|\) 個候選，合起來 \(O(|S|^2 L)\)：\(|S| = 1000\) 時不到 \(10^7\)，子題組 1 的 \(20\) 分穩穩到手。\(|S| = 5 \times 10^5\) 就不行了——候選幾乎全部出現的測資本站實測 \(3.2\) 秒，超過時限。

從 20 分到 100 分：先把 \(S\) 的每個視窗收進 set

慢在每個候選都重新掃一次 \(S\)。反過來做：先把 \(S\) 裡每一個長度 \(L\) 的子字串（視窗）放進一個 set<string>，之後檢查候選只要問 set 有沒有這個字串，\(O(\log |S|)\)。

含有 \(A\) 以外字母的視窗不用特別剔除——候選字串只用 \(A\) 的字母，永遠不會跟那種視窗相等，放進去只是多占一點空間。

#include <bits/stdc++.h>
using namespace std;

string A, S;
int L;
set<string> appeared;             // S 裡出現過的每一個長度 L 的子字串
string current;                   // 正在組的候選字串

bool search() {                   // 依字典序逐一試候選字串，找到第一個沒出現的就印出來
    if ((int)current.size() == L) {
        if (appeared.count(current) == 0) {        // 沒出現過：就是它
            cout << current << endl;
            return true;
        }
        return false;
    }
    for (char ch : A) {           // A 已經排好序：先試小的字母
        current.push_back(ch);
        if (search()) return true;
        current.pop_back();
    }
    return false;
}

int main() {
    cin >> A >> L >> S;
    for (int i = 0; i + L <= (int)S.size(); i++) appeared.insert(S.substr(i, L));
    search();
    return 0;
}

放視窗 \(O(|S| \log |S| \cdot L)\)、檢查候選最多 \(|S|\) 次，\(|S| = 5 \times 10^5\) 本站實測 \(0.18\) 秒。和 \(20\) 分版相比只換掉一件事：「S.find」變成「先收集、再查 set」，search() 一個字都沒改。

測過再交：範例沒有 \(A\) 以外的字母

兩個範例的 \(S\) 都只用 \(A\) 的字母、\(|A| \ge 2\)、\(L \ge 2\)、答案都在中間。沒蓋到的：\(|A| = 1\)、\(L = 1\)、\(A\) 以外的字母把視窗切斷、答案是字典序最後一個，以及候選幾乎全部出現的大測資（驗速度）。

六筆都親眼看過正確，這題就穩了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string A, S;
    int L;
    cin >> A >> L >> S;
    int B = A.size();
    int total = 1;
    for (int i = 0; i < L; i++) total *= B;        // B^L 種候選字串，每一種對應一個編號
    int digit[26];
    for (int i = 0; i < 26; i++) digit[i] = -1;    // -1 = 這個字母不在 A 裡
    for (int i = 0; i < B; i++) digit[A[i] - 'a'] = i;
    vector<bool> appeared(total, false);
    int code = 0, run = 0;        // code = 最近 L 個字母的編號，run = 連續幾個字母都在 A 裡
    for (char ch : S) {
        int d = digit[ch - 'a'];
        if (d == -1) {            // 不在 A 裡：視窗斷掉，重新累積
            code = 0;
            run = 0;
            continue;
        }
        code = (code * B + d) % total;             // 推進一格：最舊的那個字母被 % 掉
        run++;
        if (run >= L) appeared[code] = true;       // 湊滿 L 個字母才算一個完整的視窗
    }
    int answer = 0;
    while (appeared[answer]) answer++;             // 題目保證答案存在，不會跑出範圍
    string word(L, A[0]);
    for (int i = L - 1; i >= 0; i--) {             // 把編號還原成字串：從最後一位往前拆
        word[i] = A[answer % B];
        answer /= B;
    }
    cout << word << endl;
    return 0;
}