Chương trình C++ tìm chuỗi khớp mẫu trong từ điển

Cho từ điển (tập chuỗi) và chuỗi mẫu. Tìm chuỗi trong từ điển khớp mẫu. Từ điển ["abb", "xyz", "aab", "kmm"], mẫu "stt" → "abb", "kmm" (mẫu: 1 ký tự khác, 2 ký tự giống nhau).

Giải pháp: mã hóa mẫu thành hash. Chuỗi nào mã hóa ra hash giống mẫu thì khớp. Duyệt từ điển, so sánh hash.

Ví dụ mã nguồn

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

string stringEncode(string str) {
    unordered_map<char, int> map;
    string encoded_str = "";
    int i = 0;
    for (char ch : str) {
        if (map.find(ch) == map.end())
            map[ch] = i++;
        encoded_str += to_string(map[ch]);
    }
    return encoded_str;
}

void matchedPattern(unordered_set<string> dict, string pattern) {
    int patt_len = pattern.length();
    string hash = stringEncode(pattern);
    for (string word : dict) {
        if (word.length() == patt_len && stringEncode(word) == hash)
            cout << word << " ";
    }
}

int main() {
    unordered_set<string> dict = {"abb", "xyz", "aab", "kmm"};
    string pattern = "stt";
    matchedPattern(dict, pattern);
}

Kết quả đầu ra

kmm abb