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

Question

我有一個向量，並且需要查看該向量中的所有字符串是否是另一個給定字符串的子字符串。

如

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