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);
}
