缺字問題

https://zerojudge.tw/ShowProblem?problemid=o078

考點

• 遞迴枚舉;
• Set;
• 字串;

思路

預處理先把 s 中所有的子字串記錄下來，然後因為字串長度很小，所以可以直接透過遞迴枚舉由字典序小到大嘗試所有的可能性，只要找到一個沒有被紀錄到的字串就可以直接輸出了！

程式碼

#include <bits/stdc++.h>

using namespace std;

string t, s, ans;
int n;
set<string> st;

// idx 代表目前填到 ans 的第幾個字母
// cnt 代表目前選了多少個字母
void dfs(int idx) {
    // 如果選到 n 個
    if (idx >= n) {
        // 已經被記錄的話就忽略
        if (st.count(ans)) return;
        // 否則就是答案了
        cout << ans << endl;
        exit(0);
    }
    if (idx >= ans.size()) return;
    // 每舉目前的位置放哪個字母
    for (int i = 0; i < t.size(); i++) {
        ans[idx] = t[i];
        // 繼續 DFS，因為選了一個字母所以 idx 和 cnt 都要 + 1
        dfs(idx + 1);
    }
}

signed main() {
    cin >> t >> n >> s;
    // ans 先初始化成字母集能拼出的最小字典序字串
    ans = string(n, t[0]);
    // 紀錄下 s 中的所有子字串
    for (int i = 0; i <= s.size() - n; i++) {
        st.insert(s.substr(i, n));
    }
    // 開始枚舉
    dfs(0);
}