ZeroJudge O078: 缺字問題

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

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

範例測資

範例輸入範例輸出
第一行為一個長度為 K (1 <= K <= 10) 的小寫字母字串代表字母集合，保證字元不重複且照字元由小到大排序。
第二行為一個正整數 L (1 <= L <= 8，1 <= KL <= 6＊105)。
第三行為小寫英文字串 S (L <= |S| <= 5＊105)。		輸出滿足題目要求的最小字典序字串。
acm
2
accaamcm		ma
dp
3
dddppdpd		pdd

解題思路

使用 DFS 去將所有組合計算出來，因為可以有重複的字元，所以 DFS 的參數只需要目前相加的字串。宣告一個 Map 來紀錄有哪些組合，這邊取名叫做 MAP，當 DFS 中的字串長度 == L 時，將 MAP[字串]++ 並且 return。

跑一個 For迴圈 從 0 到 S.length()-L，並且宣告另外一個 Map 來紀錄 S 中長度為 L 的子字串有哪些，這邊取名叫 appear。在裡面再跑一個 For迴圈 從目前的 i 到 i+L，要從目前的位置加字串加到 L 的長度。加完之後將 appear[剛剛加完的字串]++。

之後跑一個 for (auto it:MAP)，要將剛剛 K 中的所有組合做判斷，如果 appear[it.first] == 0，代表 S 中沒有這個子字串，但是剛剛的 DFS 有計算出這個 it.first，這個就是答案，輸出 it.first 之後將迴圈 break。跑 for (auto it:MAP) 的時候會依照字串的順序跑，所以先跑到的就會是較小的字典序字串。

範例程式碼－ZeroJudge O078: 缺字問題

#include <iostream>
#include <map>
using namespace std;

string K, str;
int L;
map<string, int>MAP;

void DFS(string add) {
    if (add.length() == L) {
        MAP[add]++;
        return;
    }
    for (int i = 0; i<K.length(); i++) DFS(add+K[i]);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> L >> str;
    DFS("");
    map<string, int>appear;
    for (int i = 0; i<=str.length()-L; i++) {
        string tmp = "";
        for (int j = i; j<i+L; j++) tmp += str[j];
        appear[tmp]++;
    }
    for (auto it:MAP) {
        if (appear[it.first] == 0) {
            cout << it.first << "\n";
            break;
        }
    }
}

//ZeroJudge O078
//Dr. SeanXD
標籤

相關文章

發佈留言