Найти первое вхождение строки из вектора <string>

Question

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

например.

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.

Answer 1

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

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

Answer 2

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

Answer 3

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; 
    } 
};