Giải thuật Tìm kiếm Động (Dynamic Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Giải thuật tìm kiếm động, còn được gọi là "tìm kiếm khi nhập" (search-as-you-type) thường được sử dụng để thực hiện các tính năng như tự động hoàn thiện trong thanh tìm kiếm. Thuật toán này cung cấp gợi ý thời gian thực dựa trên đầu vào của người dùng và dữ liệu có sẵn.

Cách hoạt động

1. Bắt đầu với một bộ dữ liệu chứa danh sách các mục (ví dụ: từ, tên hoặc sản phẩm).
2. Khi người dùng gõ từng ký tự, cập nhật truy vấn tìm kiếm.
3. Lọc bộ dữ liệu dựa trên truy vấn tìm kiếm hiện tại.
4. Hiển thị kết quả đã lọc cho người dùng trong thời gian thực.

Ví dụ

Xem xét một bộ dữ liệu các ngôn ngữ lập trình: ["C", "C++", "Java", "Python", "JavaScript", "Ruby", "Swift"].

1. Người dùng gõ "C". Kết quả lọc: ["C", "C++"].
2. Người dùng gõ "C++". Kết quả lọc: ["C++"].
3. Người dùng gõ "Java". Kết quả lọc: ["Java", "JavaScript"].
4. Người dùng gõ "Py". Kết quả lọc: ["Python"].
5. Người dùng gõ "Jav". Kết quả lọc: ["Java", "JavaScript"].

Mã ví dụ trong C++

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> dynamicSearch(const std::vector<std::string>& dataset, const std::string& query) {
    std::vector<std::string> results;

    for (const std::string& item : dataset) {
        if (item.find(query) != std::string::npos) {
            results.push_back(item);
        }
    }

    return results;
}

int main() {
    std::vector<std::string> programmingLanguages = {"C", "C++", "Java", "Python", "JavaScript", "Ruby", "Swift"};
    std::string userQuery = "Jav";

    std::vector<std::string> suggestions = dynamicSearch(programmingLanguages, userQuery);

    std::cout << "Gợi ý cho truy vấn '" << userQuery << "': ";
    for (const std::string& suggestion : suggestions) {
        std::cout << suggestion << " ";
    }
    std::cout << std::endl;

    return 0;
}

Trong ví dụ này, hàm dynamicSearch nhận bộ dữ liệu về các ngôn ngữ lập trình và truy vấn của người dùng làm đầu vào. Nó trả về các gợi ý dựa trên truy vấn hiện tại. Khi người dùng gõ ký tự, thuật toán sẽ lọc bộ dữ liệu và hiển thị gợi ý thời gian thực.

Lưu ý: Thực hiện thực tế của tìm kiếm động có thể phức tạp hơn, bao gồm các kỹ thuật như cấu trúc trie hoặc chỉ số hiệu quả cho các bộ dữ liệu lớn.