close

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

Thuật toán Tìm kiếm theo văn bản (Text Search) là một phương pháp quan trọng trong xử lý văn bản và tìm kiếm thông tin. Thuật toán này cho phép chúng ta tìm kiếm và xác định vị trí xuất hiện của một chuỗi con (hoặc mẫu) trong một đoạn văn bản lớn hơn.

Cách hoạt động

  1. Bắt đầu với một đoạn văn bản lớn (hay tài liệu) và một chuỗi con cần tìm kiếm.
  2. Duyệt qua từng ký tự của văn bản một cách tuần tự.
  3. So sánh chuỗi con với một phần của văn bản có độ dài bằng chuỗi con. Nếu khớp, ghi nhận vị trí hiện tại.
  4. Di chuyển tới vị trí tiếp theo và tiếp tục so sánh.

Ví dụ

Xem xét đoạn văn bản: "Hãy tìm kiếm chuỗi con trong đoạn văn bản này để thấy cách thuật toán hoạt động."

Và chuỗi con cần tìm kiếm: "chuỗi con"

  1. Bắt đầu tại vị trí 0. So sánh "Hãy" với "chuỗi con". Không khớp.
  2. Di chuyển tới vị trí 1. So sánh "ãy " với "chuỗi con". Không khớp.
  3. Di chuyển tới vị trí 2. So sánh "y t" với "chuỗi con". Không khớp.
  4. Di chuyển tới vị trí 3. So sánh " tì" với "chuỗi con". Không khớp.
  5. Di chuyển tới vị trí 4. So sánh "tìm" với "chuỗi con". Không khớp.
  6. Di chuyển tới vị trí 5. So sánh "ìm " với "chuỗi con". Không khớp.
  7. Di chuyển tới vị trí 6. So sánh "m k" với "chuỗi con". Không khớp.
  8. Di chuyển tới vị trí 7. So sánh " ki" với "chuỗi con". Không khớp.
  9. Di chuyển tới vị trí 8. So sánh "kiế" với "chuỗi con". Không khớp.
  10. Di chuyển tới vị trí 9. So sánh "iếm" với "chuỗi con". Không khớp.
  11. Di chuyển tới vị trí 10. So sánh "ếm " với "chuỗi con". Không khớp.
  12. Di chuyển tới vị trí 11. So sánh "m c" với "chuỗi con". Không khớp.
  13. Di chuyển tới vị trí 12. So sánh " co" với "chuỗi con". Không khớp.
  14. Di chuyển tới vị trí 13. So sánh "con" với "chuỗi con". Khớp. Ghi nhận vị trí 13.

Chuỗi con "chuỗi con" được tìm thấy tại vị trí 13 trong đoạn văn bản.

Ví dụ mã nguồn trong C++

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

std::vector<int> textSearch(const std::string& text, const std::string& query) {
    std::vector<int> positions;

    for (int i = 0; i <= text.length() - query.length(); ++i) {
        int j = 0;
        while (j < query.length() && text[i + j] == query[j]) {
            ++j;
        }
        if (j == query.length()) {
            positions.push_back(i);
        }
    }

    return positions;
}

int main() {
    std::string text = "Hãy tìm kiếm chuỗi con trong đoạn văn bản này để thấy cách thuật toán hoạt động.";
    std::string query = "chuỗi con";

    std::vector<int> result = textSearch(text, query);

    std::cout << "Chuỗi con được tìm thấy tại các vị trí: ";
    for (int pos : result) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}

Trong ví dụ này, hàm textSearch được sử dụng để tìm các vị trí xuất hiện của chuỗi con "chuỗi con" trong đoạn văn bản. Kết quả sẽ là một vector chứa các vị trí bắt đầu của sự khớp.