Как найти, является ли строка префиксом строк, хранящихся в наборе?

Question

std::set<std::string> setStrings;

setString.insert("abc");
setString.insert("abcd");
setString.insert("babc");

Вопрос> Я хотел бы знать, как проверить, является ли «bab» одним из префиксов сохраненной строки?

Answer 1

Попробуйте использовать Trie.

http://en.wikipedia.org/wiki/Trie

Answer 2

Я предполагаю, что вы не хотите искать весь набор: просто используйте std::set<std::string>::lower_bound() и повторяйте, пока не найдете std::string, который не имеет желаемого префикса:

std::string const prefix("bab");
for (std::set<std::string>::const_iterator it(setStrings.lower_bound(prefix));
     it != setStrings.end() && it->find(prefix) == 0; ++it) {
    std::cout << "prefixed: '" << *it << "'\n";
}

Если выпросто хочу узнать, есть ли одна строка с соответствующим префиксом, вы можете использовать условие как в цикле.

Answer 3

Есть и другие способы сделать это. Это один из них:

std::set<std::string> setStrings;

setStrings.insert("abc");
setStrings.insert("abcd");
setStrings.insert("babc");

std::string prefix("bab");

std::set<std::string>::iterator i;
for (i = setStrings.begin(); i != setStrings.end(); ++i)
{
    if ((*i).compare(0, prefix.length(), prefix) == 0)
        std::cout << *i << " starts with: " << prefix << std::endl;
}

Это еще один способ:

std::set<std::string>::iterator i;
for (i = setStrings.begin(); i != setStrings.end(); ++i)
{
    if ((*i).substr(0, prefix.length()) == prefix)
        std::cout << *i << " starts with: " << prefix << std::endl;
}

Answer 4

   std::set<std::string> setString;
   setString.insert("abc");
   setString.insert("abcd");
   setString.insert("babc");
   for ( auto &i : setString ){
      std::cout << i << " result: "<< ( i.find("bab")==0) <<std::endl;
   }

это C ++ 11, но str::find работает так же, как и в старых C ++

abc result: 0
abcd result: 0
babc result: 1