close

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

Giải thuật tìm kiếm theo chuỗi được sử dụng để tìm các vị trí xuất hiện của một mẫu cụ thể (chuỗi con) trong một văn bản lớn (chuỗi). Thuật toán này đóng vai trò quan trọng trong xử lý văn bản, tìm kiếm và thao tác chuỗi.

Cách hoạt động

  1. Bắt đầu với một văn bản (chuỗi) và một mẫu (chuỗi con) cần tìm kiếm.
  2. Duyệt qua từng ký tự trong văn bản một lần.
  3. Đối với mỗi ký tự trong văn bản, so sánh nó với ký tự đầu tiên của mẫu.
  4. Nếu có sự khớp, kiểm tra xem các ký tự tiếp theo có khớp với mẫu không.
  5. Nếu mẫu được khớp hoàn toàn, ghi nhận vị trí bắt đầu của sự khớp.
  6. Tiếp tục tìm kiếm mẫu trong văn bản.

Ví dụ

Xem xét một văn bản: "ababcababcabcabc" Và một mẫu: "abc"

  1. Bắt đầu tại vị trí 0. So sánh "a" với ký tự đầu tiên "a" trong mẫu.
  2. Khớp được tìm thấy, di chuyển đến các ký tự tiếp theo: "b" với "b" và "a" với "c".
  3. Tiếp tục khớp: "b" với "a", "a" với "b" và "b" với "c".
  4. Khớp thất bại tại vị trí 2.
  5. Bắt đầu lại tại vị trí 3. So sánh "a" với ký tự đầu tiên "a" trong mẫu.
  6. Khớp thành công: "a" với "a", "b" với "b" và "c" với "c".
  7. Ghi nhận vị trí 3.

Mẫu "abc" được tìm thấy tại các vị trí 0, 6 và 9.

Mã ví dụ trong C++

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

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

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

    return positions;
}

int main() {
    std::string text = "ababcababcabcabc";
    std::string pattern = "abc";

    std::vector<int> result = stringSearch(text, pattern);

    std::cout << "Mẫu đượ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 stringSearch được sử dụng để tìm các vị trí xuất hiện của mẫu "abc" trong văn bản "ababcababcabcabc". Kết quả sẽ là một vector chứa các vị trí bắt đầu của sự khớp.