#include <algorithm>
 
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last,
                         ForwardIterator2 s_first, ForwardIterator2 s_last );
 
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last,
                         ForwardIterator2 s_first, ForwardIterator2 s_last, BinaryPredicate p );

Searches for the first subsequence of elements [s_first, s_last) in the range [first, last). One version of the function uses operator== to compare the elements, another uses the given binary predicate p.

first, last - forward iterators defining the range to be analyzed

s_first, s_last - forward iterators defining the sequence to be searched for

p - binary predicate which returns true if the elements should be treated as equal

iterator to the beginning of last subsequence [s_first, s_last) in range [first, last). If no such subsequence is found, last is returned.

First version:

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first, ForwardIterator1 last,
                        ForwardIterator2 s_first, ForwardIterator2 s_last)
{
    ForwardIterator1 t_last = first;
    std::advance(t_last, std::distance(first, last) - std::distance(s_first - s_last) + 1);
    for (; first != t_last; ++first) {
        ForwardIterator1 it = first;
        ForwardIterator2 s_it = s_first;
        while (*it == *s_it) {
            ++it; ++s_it;
            if (s_it == s_last) {
                return first;
            }
        }
    }
    return last;
}

Second version:

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first, ForwardIterator1 last,
                        ForwardIterator2 s_first, ForwardIterator2 s_last, BinaryPredicate p)
{
 
    ForwardIterator1 t_last = first;
    std::advance(t_last, std::distance(first, last) - std::distance(s_first - s_last) + 1);
    for (; first != t_last; ++first) {
        ForwardIterator1 it = first;
        ForwardIterator2 s_it = s_first;
        while (p(*it, *s_it)) {
            ++it; ++s_it;
            if (s_it == s_last) {
                return first;
            }
        }
    }
    return last;
}

does at most S*(N-S+1) comparisons where S = distance(s_first, s_last) and N = distance(first, last) comparisons.

find_end, equal, find, lexicographical_compare, mismatch, search_n