ベクトルからの最初の文字列の検索<string>

Question

の値を持つvector<string> vectorStringsがあります。私は、入力文字列中のベクトル中の文字列のどれかが最初に出現するのを発見したい。

ベクトル内の指定された文字列の

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 

この実装では動作しますが、私はブーストライブラリやSTDライブラリでこれを行うために、よりエレガントな方法が存在するかどうかを知りたいでしょう。私は、Windows上で作業して、私は、このタスクのための一般的なブーストアルゴリズムを知らないのVisual Studio 2010

Answer 1

これはMapReduceの問題です。

最初に、位置であるvector<string>からvector<int>に移動し、その値を最小値で1つの値に減らしたい場合は、縮小します。まず、地図。これは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; 
    } 
};