Найти первое вхождение строки из вектора‹строка›

У меня есть vector<string> vectorStrings со значениями: ta, bc, ac, st, cer, cda. Я хочу найти первое вхождение любой из строк в векторе во входной строке.

e.g.

InputStr = "this certainly helps";

Из заданных строк в векторе я хотел бы сказать, что "cer" было первым вхождением в позицию 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

Эта реализация работает, но я хотел бы знать, существует ли более элегантный способ сделать это с помощью библиотек повышения или стандартной библиотеки.

Я работаю над Windows и использую Visual Studio 2010.


c++ boost std
person a n    schedule 22.12.2011    source источник
comment
Я не знаю об элегантности, но я думаю, что внешний цикл должен проходить по строковым символам, а внутренний цикл (в вашем случае - поиск) по строкам в вашем векторе. мне кажется так будет эффективнее   -  person Armen Tsirunyan    schedule 23.12.2011
comment
Вы можете сделать min string::size_type min = string::npos; (что также может позволить вам избавиться от теста pos == npos).   -  person UncleBens    schedule 23.12.2011
comment
Вы можете использовать итератор. ;)   -  person Mateen Ulhaq    schedule 23.12.2011

Ответы (2)


arrow_upward
8
arrow_downward

Это проблема MapReduce.

Во-первых, вы хотите перейти от vector<string> к vector<int> их позиций, что является картой, а затем вы хотите уменьшить значения до одного значения на их минимум, что является сокращением. Во-первых, карта. Это 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);
    }
);

Теперь мы просто используем std::min_element, чтобы получить наименьший элемент, сокращение.

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

Чтобы найти строку, которая была найдена там, это простая арифметика итератора:

string found = stuff[iterator - positions.begin()];
person Puppy    schedule 22.12.2011
comment
Просто ради этого я попытался написать эквивалент C++ 03 без повышения. После того, как я вместе поиграл с указателем функции-члена для find, я вспомнил, что mem_fun_ref работает только для унарных функций. На всякий случай OP попытается сделать то же самое. - person pmr; 23.12.2011

arrow_upward
2
arrow_downward

Я не знаю общих алгоритмов повышения для этой задачи. Ваш алгоритм правильный и должен нормально работать на небольших размерах. Если у вас есть большой вектор строк, вы можете использовать более сложные древовидные структуры для этой задачи. Например, вы можете организовать свой вектор строк в виде дерева, чтобы ускорить поиск. Вы могли бы также использовать суффиксное дерево.

person nogard    schedule 22.12.2011