55 votes

Vérifier si une chaîne de caractères est le préfixe d'une autre.

J'ai deux cordes que j'aimerais comparer : String et String: . Existe-t-il une fonction de bibliothèque qui renverrait un message vrai lorsqu'on lui passe ces deux chaînes de caractères, mais faux pour, par exemple String et OtherString ?

Pour être précis, je veux savoir si une chaîne est le préfixe d'une autre.

2 votes

Et si on utilisait le bon vieux string.compare() ?

0 votes

Vous voulez dire comparer les N premiers personnages ?

0 votes

@Donotalo Ce serait bien, ce serait bien s'il le faisait pour moi afin que je n'aie pas besoin de faire de la musculation. n .

59voto

Nim Points 22570

Utilisez std::mismatch . Passez la chaîne la plus courte comme première plage d'itération et la plus longue comme deuxième plage d'itération. Le retour est une paire d'itérateurs, le premier est l'itérateur dans la première plage et le second, dans la deuxième plage. Si le premier est la fin de la première plage, alors vous savez que la chaîne courte est le préfixe de la chaîne plus longue, par ex.

std::string foo("foo");
std::string foobar("foobar");

auto res = std::mismatch(foo.begin(), foo.end(), foobar.begin());

if (res.first == foo.end())
{
  // foo is a prefix of foobar.
}

3 votes

+1, et cela peut en fait être étendu pour tester partagent un préfixe plutôt que est un préfixe en comparant le résultat avec begin() plutôt que la fin (et on peut aussi obtenir la longueur réelle du préfixe commun, en soustrayant)

11 votes

+1, mais cela est dangereux si la deuxième chaîne est plus courte car vous itérerez au-delà de sa fin. il est donc nécessaire de vérifier que foo.size() <= foobar.size() .

0 votes

@Benoit, yip ; la chose qui me dérange est qu'ils auraient pu si facilement accepter une fin pour le deuxième itérateur et nous éviter de devoir faire la vérification avant...

22voto

Neil Mayhew Points 2579

C'est à la fois efficace et pratique :

str.compare(0, pre.size(), pre) == 0

compare est rapide parce qu'il utilise le système rapide traits::compare et ne doit pas copier de données.

Ici, il comparera std::min(str.size(), pre.size()) mais si les caractères des deux plages sont égaux, il vérifie également la longueur des caractères de l'échantillon. pre et renvoie une valeur non nulle si pre est plus long que ça.

Voir la documentation à cplusplus.com.

J'ai écrit un programme de test qui utilise ce code pour comparer les préfixes et les chaînes de caractères donnés sur la ligne de commande.

19voto

James Kanze Points 96599

Si vous savez quelle chaîne est la plus courte, la procédure est simple, il suffit d'utiliser std::equal avec la chaîne la plus courte en premier. Si vous ne le faites pas, quelque chose quelque chose comme ce qui suit devrait fonctionner :

bool
unorderIsPrefix( std::string const& lhs, std::string const& rhs )
{
    return std::equal(
        lhs.begin(),
        lhs.begin() + std::min( lhs.size(), rhs.size() ),
        rhs.begin() );
}

16voto

MSalters Points 74024

std::string(X).find(Y) est nul si et seulement si Y est un préfixe de X

4 votes

Ce n'est probablement pas le plus efficace. Le compilateur devrait le mettre en ligne, ou alors il doit rechercher Y à des décalages non nuls également.

5 votes

C'est concis, mais potentiellement inefficace (imaginez si X est très longue et Y es no le préfixe de X ).

1 votes

@FrerichRaabe : C'est la raison pour laquelle j'ai moi-même fait un commentaire à ce sujet. Un bon optimiseur repérera la comparaison avec zéro, trouvera que le comparant correspond à la variable d'index utilisée dans le précédent. for et remplacer la for boucle par un if déclaration.

9voto

Vlad Points 7354

Avec string::compare vous devriez être capable d'écrire quelque chose comme :

bool match = (0==s1.compare(0, min(s1.length(), s2.length()), s2,0,min(s1.length(),s2.length())));

Alternativement, dans le cas où nous ne voulons pas utiliser l'option length() fonction membre :

bool isPrefix(string const& s1, string const&s2)
{
    const char*p = s1.c_str();
    const char*q = s2.c_str();
    while (*p&&*q)
        if (*p++!=*q++)
            return false;
    return true;
}

0 votes

Cette méthode est potentiellement inefficace si string1 est très longue - en appelant length() est O(n) et il n'y a pas besoin de connaître la longueur exacte de la chaîne. Il suffit de savoir si elle est suffisamment longue ou non.

0 votes

Je ne pense pas que ce soit le cas, pas avec std::string . D'après ce que je peux voir dans basic_string.h, il y a un champ de longueur quelque part.

4 votes

.length() is O(n) ? Est-ce que par hasard vous regardez le character_traits la table ?

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X