C++ Find last ocurrence of a string inside a substring

Question

I need a method that helps me to find a string inside another substring, or in other words, find a string inside a subrange of other string. Besides, I need to find it in reverse order because I know that the string I'm looking for is closed to the end of the substring used as "haystack".

Let's suppose the following piece of code, where rfind_in_substr is the method I'm asking for:

std::string sample("An example with the example word example trice");

// substring "ample with the example wo"
std::size_t substr_beg = 5;
std::size_t substr_size = 24;

// (1)
std::size_t pos = rfind_in_substr(sample, substr_beg,
                                  substr_size, "example");

// pos == 20, because its the index of the start of the second
// "example" word inside the main string. 

Of course, the line (1) could be replaced by:

std::size_t pos = substr_beg + sample.substr
            (substr_beg, substr_size).rfind("example");

But that implies an unnecesary copy of the substring. Is there any method or C++/boost method that could help me doing that?

I was looking at boost::algorithm::string library but I've found nothing (that I had understood). I know that C++17 has the std::string_view class, that would be perfect, but I'm using C++14.

Answer 1

From Boost.StringAlgo:

#include <boost/algorithm/string/find.hpp>

auto haystack = boost::make_iterator_range(str.begin() + from, str.begin() + from + len);
auto found = boost::algorithm::find_last(haystack, needle);

Now, if you need to use this with other member functions from std::string, you need to do extra steps in converting a resulting range into an index like this answer does, but if you aren't, then simply use the range interface and avoid the std::string's "helpful" methods.

Another option is to use boost::string_ref which is what std::string_view is basically based on:

#include <iostream>
#include <boost/utility/string_ref.hpp>


std::size_t rfind_in_substr(std::string const& str, std::size_t from,
                            std::size_t len, std::string const& s)
{

    return from + boost::string_ref(str).substr(from, len).rfind(s);
}

int main()
{
    std::string sample("An example with the example word example trice");

    // substring "ample with the example wo"
    std::size_t substr_beg = 5;
    std::size_t substr_size = 24;

    // (1)
    std::size_t pos = rfind_in_substr(sample, substr_beg,
                                      substr_size, "example");

    // pos == 20, because its the index of the start of the second
    // "example" word inside the main string. 
    std::cout << pos << "\n";
}

Answer 2

You can find the answer by combining an API that limits the search within the original string by length and an additional check to see if the end result comes prior to substr_beg:

std::size_t rfind_in_substr(
    const std::string& str
,   const std::size_t from
,   const std::size_t len
,   const std::string& sub
) {
    std::size_t res = str.rfind(sub, from+len-sub.size());
    return res != string::npos && res >= from ? res : string::npos;
}

• from+len-sub.size() computes the last position at which the substring could start.
• res >= from rejects an answer if it comes before the initial character of substring.

Demo.

Answer 3

With std::find_end the problem can be solved efficiently without using more than needed, but I hoped there was any method that already solved that:

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

std::size_t rfind_in_substr(std::string const& str, std::size_t from,
                            std::size_t len, std::string const& s)
{
    auto sub_beg = str.begin() + from;
    auto sub_end = sub_beg + len;

    auto found_it = std::find_end(sub_beg, sub_end, s.begin(), s.end());

    if (found_it == sub_end)
        return str.npos;
    else
        return found_it - str.begin();
}

int main()
{
    std::string sample("An example with the example word example trice");

    // substring "ample with the example w"
    std::size_t substr_beg = 5;
    std::size_t substr_size = 24;

    std::size_t pos = rfind_in_substr(sample, substr_beg,
                                      substr_size, "example");

    std::cout << pos << std::endl; // Prints 20
}