如何搜索字符串是否是存储在集合中的字符串的前缀？

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

如果您只想查找是否有一个带有相应前缀的字符串,则可以使用循环中的条件.