查找向量中的所有元素是否在字符串中

Question

我有一个向量，并且需要查看该向量中的所有字符串是否是另一个给定字符串的子字符串。查找向量<string>中的所有元素是否在字符串中

如

vector<string> v; 
v.push_back("str1"); 
v.push_back("str2"); 
string s1 = "str1, str2, str3"; 
string s2 = "str1, str3"; 

有没有办法从S1和S2，从假获得真正的没有遍历向量？另外，请注意，由于我的环境，我不能使用提升。我想如果我有提升，我可以做到这一点。

Answer 1

Boost不是魔术。它只会循环播放该矢量。这取决于你需要这种效率的效率;如果它不是时间密集型的，那就写简单的循环。

（顺便说一句，如果你想知道如何确定是否一个字符串包含另一个作为一个子字符串，使用mystring.find(mysubstring)。）

---

编辑：我可能已经有点表露无疑与我第一反应，所以我会详细说明。如果你对效率感兴趣，你可以通过一次大字符串来完成，如果主字符串比子字符串长得多，这将是一个改进。

下的运行时间为O(km + kn)，那里有最大长度m的k子，我们在各自的长度n的字符串检查（而不是天真的算法，这是O(kmn)）。

#include <cassert> 
#include <list> 
#include <map> 
#include <string> 

// store the substrings in a Trie data structure (http://en.wikipedia.org/wiki/Trie) 
class Trie { 
public: 
    friend class TrieCounter; 

    Trie(): m_parent(0) {} 
    ~Trie() { for(Leaves::iterator it=m_leaves.begin();it!=m_leaves.end();++it) delete it->second; } 

    const Trie *add(const char *str) { 
    Leaves::iterator it = m_leaves.find(str[0]); 
    if(it == m_leaves.end()) 
     it = m_leaves.insert(std::make_pair(str[0], new Trie(this))).first; 

    if(!str[0]) 
     return it->second; 
    return it->second->add(str + 1); 
    } 

    const Trie *get(char c) const { 
    Leaves::const_iterator it = m_leaves.find(c); 
    if(it == m_leaves.end()) 
     return 0; 
    return it->second; 
    } 

    bool is_leaf() const { return m_leaves.empty(); } 
    bool is_end_of_word() const { return m_leaves.find(0) != m_leaves.end(); } 

private: 
    Trie(Trie *parent): m_parent(parent) {} 

private: 
    Trie *m_parent; 
    typedef std::map<char, Trie*> Leaves; 
    Leaves m_leaves; 
}; 

// a little counter helper class 
class TrieCounter { 
public: 
    TrieCounter(const Trie& root): m_wordCount(0) { add(root); } 

    unsigned word_count() const { return m_wordCount; } 
    void use(const Trie& trie) { 
    m_wordCount++; 
    decr(trie); 
    } 

private: 
    void add(const Trie& trie) { 
    if(trie.is_leaf()) 
     return; 

    m_count[&trie] = trie.m_leaves.size(); 
    for(Trie::Leaves::const_iterator it=trie.m_leaves.begin();it!=trie.m_leaves.end();++it) 
     add(*it->second); 
    } 

    void decr(const Trie& trie) { 
    Count::iterator it = m_count.find(&trie); 
    assert(it != m_count.end()); 
    assert(it->second > 0); 
    it->second--; 
    if(it->second == 0) 
     decr(*it->first->m_parent); 
    } 

private: 
    typedef std::map<const Trie*, unsigned> Count; 
    Count m_count; 
    unsigned m_wordCount; 
}; 

// and the list of substrings 
class WordList { 
public: 
    WordList() {} 
    void add(const std::string& str) { m_wordEnds.push_back(m_trie.add(str.c_str())); } 
    unsigned size() const { return m_wordEnds.size(); } 
    const Trie& root() const { return m_trie; } 

private: 
    Trie m_trie; 
    typedef std::list<const Trie *> Tries; 
    Tries m_wordEnds; 
}; 

unsigned count_in(const WordList& wordList, const std::string& str) { 
    typedef std::list<const Trie *> Tries; 
    typedef Tries::iterator Iter; 

    TrieCounter counter(wordList.root()); 
    Tries curChecking; 
    for(unsigned i=0;i<str.size();i++) { 
    const char c = str[i]; 
    curChecking.push_back(&m_wordList.root()); 

    Iter it = curChecking.begin(); 
    while(it != curChecking.end()) { 
     Iter next = ++Iter(it); 
     if(const Trie *child = (*it)->get(c)) { 
     *it = child; 
     if(child->is_end_of_word()) 
      counter.use(*child); 
     } else { 
     curChecking.erase(it); 
     } 
     it = next; 
    } 
    } 
    return counter.word_count(); 
} 

首先设置字符串：

WordList wordList; 
wordList.add("foo"); 
wordList.add("lan"); 
wordList.add("found"); 
wordList.add("under"); 
wordList.add("next"); 
wordList.add("land"); 
wordList.add("new"); 
wordList.add("news"); 
wordList.add("on"); 
wordList.add("and"); 

然后

std::cout << count_in(wordList, "newfoundland") << "\n"; 

Answer 2

它使用标准模板库的算法。他们在内部循环字符串，但这可能是您要查找的内容。

bool in(string string1,string string2){ 
    return string2.find(string1) != string::npos; 
} 

if (count_if(v.begin(),v.end(),bind2nd(ptr_fun(in),s1)) == v.size()){ 
    cout << "all match" << endl; 
} 

如果你的编译器支持C++ 0x lambdas，你可能会发现lambda更清晰。

if (count_if(v.begin(),v.end(), 
    [&](string substr){return s1.find(substr)!=string::npos;}) 
    == v.size()){ 
    cout << "all match" << endl;; 
}