C++：サブストリングの配列内の文字列を効率的に見つける

Question

私は文字列接頭辞の配列を持っています：std::vector<std::string> haystack = {"/bin/", "/usr/bin/", "/usr/local/bin/"}。

std::string needle = "/bin/echo"は、標準C++ライブラリを使用してhaystackのサブストリングで始まることがわかりますか。

正確な一致を見つける必要がある場合は、効率的なバイナリ検索を実行するstd::set<std::string>を使用できますが、文字列の最初の部分だけを一致させる必要があるため、現在は単純な方法ループ：文字列の長さの降順によって

for (auto it = haystack.begin(); it != haystack.end(); it++) { 
    if (needle.compare(0, it->size(), *it) == 0) { 
     return true; // Found it 
    } 
} 
return false; 

Answer 1

hasystack
1. ソート。
2. 接頭辞はneedle以下の順番で比較してください。右から左へ。 E. prefixが5文字の場合、prefix[4]をneedle[4]と、次にprefix[3]をneedle[3]と比較してください。

この方法で、多くの不一致を即座に破棄します。ボーナスとして、あなたは最も長い試合を最初に見つけるでしょう（あなたが望むものかもしれません）。

Answer 2

私は追加したい1「最適化は、」あなたは、あなたがstd::any_ofを使用している場合、それはあなたがストリングがマッチしたを検索する場合はそれ以外の場合は最初のサブストリングの一致

auto found = std::any_of(begin(haystack), 
         end(haystack), 
         [&needle](std::string const& sub) 
         { 
          return needle.compare(0, sub.size(), sub) == 0; 
         }); 

を発見すると短絡するということですstd::find_ifを使用することもできます。これは、最初の一致が見つかると短絡します。

auto match = std::find_if(begin(haystack), 
          end(haystack), 
          [&needle](std::string const& sub) 
          { 
           return needle.compare(0, sub.size(), sub) == 0; 
          });