Recherche si tous les éléments d'un vecteur <string> sont dans une chaîne

Question

J'ai un vecteur et j'ai besoin de voir si toutes les chaînes de ce vecteur sont des sous-chaînes d'une autre chaîne donnée.

par exemple

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

Y at-il un moyen d'obtenir le vrai du faux s1 et de s2 sans boucle sur le vecteur? Notez également qu'en raison de mon environnement, je ne peux pas utiliser boost. Je pense que si j'avais boost, je pourrais le faire.

Answer 1

Boost n'est pas magique. Il va juste boucler sur ce vecteur aussi. Cela dépend de l'efficacité dont vous avez besoin; Si ce n'est pas long, alors écrivez simplement la boucle simple.

(Soit dit en passant, si vous vous demandez comment déterminer si une chaîne contient un autre comme une sous-chaîne, utilisez mystring.find(mysubstring).)

---

Edit: je peut-être été un peu snarky avec mon première réponse, donc je vais élaborer. Si vous êtes intéressé par l'efficacité, vous pouvez le faire avec un passage de la grande chaîne, ce qui sera une amélioration si la chaîne principale est beaucoup plus longue que les sous-chaînes.

La durée de ce qui suit est O(km + kn), où il y a k sous-chaînes de longueur max m, et nous vérifions dans une chaîne de longueur n (par opposition à l'algorithme naïf, qui est 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(); 
} 

d'abord votre sous-chaînes:

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

puis

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

Answer 2

Il utilise les algorithmes dans la bibliothèque de modèles standard. Ils passent en boucle sur la chaîne en interne, mais c'est peut-être ce que vous cherchez.

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

Si votre compilateur prend en charge lambdas 0x C +, vous pourriez trouver un lambda être plus claire.

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