Encontrar la primera aparición de una cadena de un vector <string>

Question

Tengo un vector<string> vectorStrings con valores: ta, bc, ac, st, cer, cda. Quiero encontrar la primera aparición de cualquiera de las cadenas en el vector en una cadena de entrada.

p. Ej.

InputStr = "this certainly helps"; 

de la cadena indicada en el vector, me gustaría una manera de decir "cer" fue la primera vez que aparece en la posición 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 

Esta aplicación funciona, pero me gustaría saber si existe una forma más elegante de hacer esto con bibliotecas Boost o biblioteca std.

estoy trabajando en Windows y utilizando Visual Studio 2010.

Answer 1

Este es un problema de MapReduce.

En primer lugar, desea pasar de vector<string> a vector<int>, de sus posiciones, que es un mapa, y luego desea reducir los valores a un valor por su mínimo, que es una reducción. Primero, el mapa. Esto es 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); 
    } 
); 

Ahora simplemente usamos std::min_element para obtener el elemento más pequeño, la reducimos.

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

Para encontrar la cadena que se encuentra allí, que es un poco simple de la aritmética iterador:

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

Answer 2

No sé algoritmos genéricos impulso para esta tarea. Su algoritmo es correcto y debería funcionar bien en dimensiones pequeñas. Si tiene un vector grande de cadenas, es posible que desee utilizar estructuras de árbol un poco más complicadas para esta tarea. Por ejemplo, puede organizar su vector de cadenas en árbol para acelerar la búsqueda. También podría usar el árbol de sufijos.

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