Нахождение всех элементов в векторе <string>в строке

Question

У меня есть вектор, и мне нужно посмотреть, все ли строки в этом векторе являются подстроками другой данной строки.

Например,

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

Есть ли способ получить значение trues1 и false от s2 без зацикливания вектора?Также обратите внимание, что из-за моего окружения я не могу использовать повышение.Я думаю, что если бы у меня было повышение, я мог бы сделать это.

Answer 1

Используются алгоритмы из стандартной библиотеки шаблонов. Они зацикливаются внутри строки, но это может быть то, что вы ищете.

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, вы можете найти лямбду более понятным.

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

Answer 2

Повышение не волшебство. Это просто зациклит этот вектор тоже. Это зависит от того, насколько эффективно вам это нужно; если это не требует много времени, просто напишите простой цикл.

(Кстати, если вам интересно, как определить, содержит ли строка другую в качестве подстроки, используйте mystring.find(mysubstring).)

---

Редактировать: Возможно, я был немного раздражительным с моим первым ответом, поэтому я уточню. Если вы заинтересованы в эффективности, вы можете сделать это за один проход большой строки, что будет лучше, если основная строка будет намного длиннее подстрок.

Время выполнения следующего: O(km + kn), где есть k подстрок максимальной длины m, и мы проверяем строку длиной 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";