std::vector 내부 요소에서 시퀀스 찾기 (find sub-sequence)

 

<algorithm>에 정의되어 있는 std::search 함수를 사용하면 쉽게 구현할 수 있다

template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2);

Search range for subsequence
Searches the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found.

The elements in both ranges are compared sequentially using operator == (or pred, in version (2)): A subsequence of [first1,last1) is considered a match only when this is true for all the elements of [first2,last2).

This function returns the first of such occurrences. For an algorithm that returns the last instead, see find_end.

 

예를 위해 "Hello,World!" 문자들로 이루어진 바이트형 벡터에서 'lo' 문자열 시퀀스의 인덱스를 가져와보자

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

int main()
{
    std::vector<uint8_t> origin = { 'H', 'e', 'l', 'l', 'o', ',', 'W', 'o','r' ,'l' ,'d', '!'};
    std::vector<uint8_t> find = { 'l', 'o' };
    std::vector<size_t> indexes{};

    auto it{ origin.begin() };
    while ((it = std::search(it, origin.end(), find.begin(), find.end())) != origin.end()) {
        indexes.push_back(std::distance(origin.begin(), it++));
    }

    for (auto const element : origin) {
        std::cout << element;
    }
    std::cout << std::endl;

    for (auto const element : indexes) {
        std::cout << element << std::endl;
    }
}

출력 결과

Hello,World!
3

 

시퀀스가 여러개 존재할 경우

std::vector<int> origin = { 1, 2, 3, 4, 5, 2, 3, 6, 7, 2, 3, 1, 2, 3, 2, 4 };
std::vector<int> find = { 2, 3 };

출력결과

1234523672312324
1
5
9
12

 

[참고]

https://www.cplusplus.com/reference/algorithm/search/

https://codereview.stackexchange.com/questions/179214/finding-subsequences-of-vector-from-a-vector