Trova la prima occorrenza di una stringa da un vettore <string>

Question

Ho un vector<string> vectorStrings con valori: ta, bc, ac, st, cer, cda. Voglio trovare la prima occorrenza di qualsiasi stringa nel vettore in una stringa di input.

ad es.

InputStr = "this certainly helps"; 

delle stringhe riportate nel vettore, vorrei un modo per dire "cer" è stata la prima occorrenza in posizione 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 

Questa implementazione funziona, ma vorrei sapere se esiste un modo più elegante per fare questo con le librerie Boost o librerie std.

Sto lavorando su Windows e utilizzando Visual Studio 2010.

Answer 1

Questo è un problema di MapReduce.

Per prima cosa, passare da vector<string> a vector<int>, delle loro posizioni, che è una mappa, e quindi si desidera ridurre i valori ad un valore del loro minimo, che è una riduzione. Innanzitutto, la mappa. Questo è 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); 
    } 
); 

Ora usiamo semplicemente std::min_element per ottenere il più piccolo elemento, la riduciamo.

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

Per trovare la stringa che è stata trovata lì, è un po 'di semplice iteratore aritmetica:

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

Answer 2

Non so algoritmi generici spinta per questo compito. Il tuo algoritmo è corretto e dovrebbe funzionare bene su piccole dimensioni. Se hai un grosso vettore di stringhe potresti voler usare strutture ad albero un po 'più complicate per questa attività. Ad esempio, puoi organizzare il tuo vettore di stringhe nell'albero per accelerare la ricerca. Puoi anche usare l'albero del suffisso.

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