std::search

#include <algorithm>

// So sánh bằng toán tử ==
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2);

// Sử dụng hàm vị từ so sánh
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                         BinaryPredicate pred);

Tìm kiếm sự xuất hiện đầu tiên của một dãy con (subsequence) trong một phạm vi (range) lớn hơn. Nó tương tự như find_end() nhưng tìm kiếm sự xuất hiện đầu tiên thay vì cuối cùng.

Tham số

first1

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi lớn hơn (nơi cần tìm kiếm).

last1

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi lớn hơn.

first2

• Forward Iterator trỏ đến phần tử đầu tiên trong dãy con cần tìm kiếm.

last2

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong dãy con cần tìm kiếm.

pred

• Một hàm vị từ (binary predicate) nhận hai đối số (một phần tử từ phạm vi lớn và một phần tử từ dãy con) và trả về true nếu hai phần tử được coi là khớp, false nếu không. (Phiên bản 2)

Giá trị trả về

• Iterator trỏ đến phần tử đầu tiên của sự xuất hiện đầu tiên của dãy con [first2, last2) trong phạm vi [first1, last1).
• Nếu không tìm thấy dãy con trong phạm vi, hàm trả về last1.

Đặc điểm

1. search() tìm kiếm sự xuất hiện đầu tiên của dãy con. Để tìm sự xuất hiện cuối cùng, hãy sử dụng find_end().
2. Phạm vi [first1, last1) và [first2, last2) là "nửa mở", không bao gồm phần tử last1 và last2.
3. Phiên bản 1 của search() sử dụng toán tử == để so sánh các phần tử. Phiên bản 2 cho phép bạn tùy chỉnh cách so sánh bằng hàm vị từ.
4. search() thường được sử dụng để:
   • Tìm kiếm một mẫu (pattern) trong một chuỗi hoặc văn bản.
   • Xác định xem một dãy con có tồn tại trong một dãy lớn hơn hay không.
   • Tìm vị trí bắt đầu của một dữ liệu cụ thể trong một tập hợp dữ liệu.
5. Độ phức tạp của search() trong trường hợp xấu nhất là O(m*n), trong đó n là độ dài của phạm vi lớn và m là độ dài của dãy con. Có những thuật toán tìm kiếm chuỗi hiệu quả hơn (ví dụ: Knuth-Morris-Pratt, Boyer-Moore) cho các trường hợp đặc biệt.

Ví dụ

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

// Hàm vị từ so sánh hai ký tự (không phân biệt hoa thường)
bool caseInsensitiveCompare(char a, char b) {
  return std::tolower(a) == std::tolower(b);
}

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5, 1, 2, 3, 6};
  std::vector<int> subsequence = {1, 2, 3};

  // Phiên bản 1: Tìm kiếm sự xuất hiện đầu tiên của {1, 2, 3}
  std::vector<int>::iterator it = std::search(numbers.begin(), numbers.end(), subsequence.begin(), subsequence.end());

  if (it != numbers.end()) {
    std::cout << "Subsequence {1, 2, 3} found at position: " << (it - numbers.begin()) << std::endl;
  } else {
    std::cout << "Subsequence {1, 2, 3} not found.\n";
  }

  std::string text = "This is a TeSt string, TeSt case.";
  std::string pattern = "test";

  // Phiên bản 2: Tìm kiếm không phân biệt hoa thường
  std::string::iterator it2 = std::search(text.begin(), text.end(), pattern.begin(), pattern.end(), caseInsensitiveCompare);

  if (it2 != text.end()) {
    std::cout << "Pattern 'test' (case-insensitive) found at position: " << (it2 - text.begin()) << std::endl;
  } else {
    std::cout << "Pattern 'test' not found (case-insensitive).\n";
  }

  return 0;
}