Find first occurrence of a string from a vector<string>

Question

I have a vector<string> vectorStrings with values: ta, bc, ac, st, cer, cda. I want to find the first occurrence of any of the strings in the vector in an input string.

e.g.

InputStr = "this certainly helps";

Of the given strings in the vector, I would want a way to say "cer" was the first occurrence at position 5.

---

int min = 9999999;
string first;

for(int i = 0; i < vectorStrings.size(); i++)
{
    int pos = InputStr.find(vectorStrings[i]);

    if(pos == string::npos)
        continue;

    if(pos < min)
    {
        min = pos;
        first = vectorStrings[i];
    }
}

// values of min and first gives which string occurred first
// and at the position of it in the input string

This implementation works, but I would want to know if there exists a more elegant way to do this with boost libraries or std library.

I am working on Windows and using Visual Studio 2010.

Answer 1

This is a MapReduce problem.

First, you want to go from vector<string> to vector<int>, of their positions, which is a map, and then you want to reduce the values to one value by their minimum, which is a reduction. First, the map. This is std::transform.

std::vector<std::string> stuff;
std::string input;
// fill stuff and input
std::vector<int> positions;
std::transform(
    stuff.begin(), 
    stuff.end(), 
    std::back_inserter(positions), 
    [&](std::string& stuff) {
        return input.find(stuff);
    }
);

Now we simply use std::min_element to get the smallest element, the reduce.

auto iterator = std::min_element(positions.begin(), positions.end());
int index = *iterator;

To find the string that was found there, it's a simple bit of iterator arithmetic:

string found = stuff[iterator - positions.begin()];

Answer 2

class Find
{
public:
    std::vector<std::string> vectorStrings;
    std::map<size_t, std::string> positions;

    size_t find(std::string str)
    {
        for(std::vector<std::string>::iterator i = vectorStrings.begin();
            i != vectorStrings.end();
            ++i)
        {
            positions[str.find(*i)] = *i;
        }

        return (*(positions.begin())).first;
    }
};

Answer 3

I don't know generic boost algorithms for this task. Your algorithm is correct and should work fine on small dimensions. If you have large vector of strings you might want to use a bit more complicated tree structures for this task. For example, you can organize your vector of strings into tree to speed up the search. You could you use suffix tree as well.