Znajdź pierwsze wystąpienie ciągu znaków z wektora <string>

Question

Mam vector<string> vectorStrings z wartościami: ta, bc, ac, st, cer, cda. Chcę znaleźć pierwsze wystąpienie któregokolwiek z ciągów w wektorze w ciągu wejściowym.

np.

InputStr = "this certainly helps"; 

danego ciągi w wektorze, chciałbym sposób powiedzieć "cer" było pierwsze wystąpienie w pozycji 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 

Ta implementacja działa, ale chciałbym wiedzieć, czy istnieje bardziej elegancki sposób to zrobić z bibliotekami podwyższenie lub std biblioteki.

pracuję na Windows i przy użyciu Visual Studio 2010.

Answer 1

To jest problem związany z MapReduce.

Po pierwsze, chcesz przejść od vector<string> do vector<int>, ich pozycji, która jest mapą, a następnie chcesz zmniejszyć wartości do jednej wartości o ich wartość minimalną, która jest redukcją. Najpierw mapa. To jest 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); 
    } 
); 

Teraz wystarczy użyć std::min_element uzyskać najmniejszy element, redukować.

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

Aby znaleźć ciąg znaków, który został tam znaleźć, jest to prosty kawałek iteratora arytmetyki:

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

Answer 2

nie wiem rodzajowe algorytmy impuls dla tego zadania. Twój algorytm jest poprawny i powinien działać poprawnie na małych wymiarach. Jeśli masz duży wektor ciągów, możesz użyć nieco bardziej skomplikowanych struktur drzewa do tego zadania. Na przykład możesz uporządkować wektor ciągów w drzewo, aby przyspieszyć wyszukiwanie. Możesz również użyć drzewa przyrostków.

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