Si le titre semble bizarre, voici une autre explication:
Si j'ai une plage a , et je veux compter combien de fois une autre plage B est apparue dans la plage a , y a-t-il un Si non, y a-t-il un moyen simple de le faire (OFC I peut boucle manuellement en boucle manuellement en utilisant std :: fonction pour le faire?
std :: Rechercher - Je parle de quelque chose de plus élégant)?
4 Réponses :
Vous pouvez utiliser std :: comte_if sur la plage A avec une lambda qui utilise std :: Trouver sur la plage b.
EDIT: remplacé std :: Recherche avec std :: Trouver.
Je pense que vous aurez besoin de construire votre propre. Voici ce qui vient à mon esprit comme une implémentation.
int main() {
std::vector<int> haystack = {1, 19, 7, 23, 2, 19, 19, 19, 19};
std::vector<int> needle = {19, 19};
assert(subsequence_count(begin(haystack), end(haystack), begin(needle), end(needle) == 3);
}
Si vous voulez le faire plus efficacement que Il y a une très belle description ici ( Cela fait référence au livre de Skiena Le manuel de design d'algorithme , qui est là que j'ai lu à leur sujet).
PS J'ai commencé à rechercher des implémentations suffixe de l'arbre C ++. Il existe plusieurs questions utiles sur StackoverFlow à ce sujet, mais rien dans STD dans la mesure du possible.
modifier pour ajouter algorithme alternatif
sur deuxième pensées, je pense que boyer-moore String Correspondant est probablement une meilleure solution, notamment car il y a un
5 commentaires
Ce n'est pas n ^ 2 ... Pour chaque élément de la plage, vous ne lisez qu'un seul élément de l'autre plage.
@Nosenseetal Voulez-vous dire que c'est vraiment
Je suppose que, par exemple, pensez à Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa et aaaaab, aussi: Complexité à la plupart des comparaisons S * N où S = STD :: Distance (S_First, S_Last) et N = STD :: Distance (Dernière Dernière).
Je mets
Boter Moore ne fonctionne pas sur des données personnalisées ... "L'algorithme alloue deux tables internes. Le premier est proportionnel à la longueur du motif; la seconde a une entrée pour chaque membre de l'alphabet" dans le motif. Pour ( Types de caractères 8 bits), cette table contient 256 entrées. "Donc, pour la table Int a 4Gentres: D O (nm) , pour m caractères dans le motif, n dans la chaîne à Soyez recherché, vous pouvez envisager un arbre
O (nm) où il y a des caractères dans le motif? En supposant que je modifie ma réponse.
O (n ^ 2) Je suppose que le motif était en général une fraction de la chaîne à rechercher, mais c'est plutôt paresseux et O (nm) est mieux.
En cas de doute, utilisez Boost :)
#include <boost/algorithm/string/finder.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/foreach.hpp>
using namespace std;
using namespace boost;
using boost::algorithm::find_all;
int main(int argc, char* argv[])
{
std::vector<double> haystack{11.0,22.0,33.0,22.0,33.0,44.0,22.0,33.0,22.0};
std::vector<double> needle{22.0,33.0};
std::vector<boost::iterator_range<std::vector<double>::iterator>> out;
boost::algorithm::find_all(out, haystack, needle);
cout << "matches=" << out.size() << endl;
cout << endl;
}
Je suppose qu'il n'y a pas de fonction standard de ce type, car il n'est pas clair si cela devrait compter des allumettes recouvertes
@Anatolyg True, en fait, la motivation pour cela me faisait aider certains jeunes programmeurs aspirants à compter tous les mots dans une séquence ... et nous avons discuté de ("AAAB", "AA") 2 ou 1.: D
@Anatolyg svn.boost.org/trac/boost/ticket/7784 . ..