liệt kê các xâu wildcard theo thứ tự từ điển

Đề bài

Trong các ứng dụng xử lý văn bản, người ta cho phép sử dụng phương thức tìm kiếm tương tự bằng cách sử dụng ký tự wildcard thay thế cho ký tự nguyên âm chưa xác định. Khi muốn tìm các xâu tương tự xâu S, người ta sẽ nhập xâu S trong đó có một số ký tự sử dụng wildcard là dấu ? để thay thế cho một trong các ký tự nguyên âm “a”, “o”, “e”, “i”, “u”.

Ví dụ xâu S=”comp??ter” ta sẽ được kết quả là các xâu “compaater”; … ; “compaoter” ; “compoiter” ; ….

Yêu cầu:

Liệt kê các xâu chỉ chứa các ký tự in thường có độ dài K ký tự tương tự xâu S theo thứ tự từ điển.

Dữ liệu:

• Dòng duy nhất ghi xâu S là xâu gốc. Độ dài xâu S không quá 20.

Kết quả:

• In ra các xâu có K ký tự tương tự xâu S theo thứ tự từ điển. Mỗi xâu in trên một dòng.

Ví dụ:

compater
competer
compiter
compoter
computer

Hướng dẫn:

Sử dụng kỹ thuật Đệ quy – Quay lui để xét các trường hợp có thể ở vị trí là dấu ? trong xâu S.

Để các phương án xuất ra đảm bảo theo thứ tự từ điển thì khi xét các phương án có thể, ta lần lượt xét theo thứ tự từ điển của các ký tự $a \rightarrow e \rightarrow i \rightarrow o \rightarrow u$

Chương trình tham khảo:

#include <bits/stdc++.h>

using namespace std;
string vowels = "aeiou";
void generate_replacements(string s, int index, vector<string>& result) {
    if (index == s.length()) {
        result.push_back(s);
        return;
    }

    if (s[index] == '?') {
        for (int i=0;i<vowels.length();i++) {
            s[index] = vowels[i];
            generate_replacements(s, index + 1, result);
            // Đặt lại ký tự "?" sau mỗi lần thử
            s[index] = '?';
        }
    } else {
        // Nếu ký tự không phải là "?", đi đến vị trí ký tự tiếp theo
        generate_replacements(s, index + 1, result);
    }
}

int main() {
    string S ; 
    cin>>S;
    vector<string> result;
    generate_replacements(S, 0, result);
    // In kết quả
    for (string s : result) {
        cout << s << endl;
    }
    return 0;
}