Fonction en C ++ pour trouver si un mot est préfixe

Question

Disons que j'ai quelques mots AB, AAB, AA.

AB est pas un préfixe à AAB mais AA est un préfixe à AAB parce que si je viens d'ajouter B à la fin des AA, il deviendra AAB, ce qui est impossible avec AB.

Alors, est-il une fonction en c ++ (STL) afin que je puisse déterminer de deux mots si l'on est à l'autre préfixe?

Merci.

Answer 1

template<class C, class T, class A>
bool starts_with(std::basic_string<C,T,A> const& haystack,
                 std::basic_string<C,T,A> const& needle)
{
  return needle.length() <= haystack.length() &&
    std::equal(needle.begin(), needle.end(), haystack.begin());
}

Notez que la vérification de la longueur n'est pas l'optimisation prématurée, il est nécessaire de répondre std :: condition sine qua non de l'égalité.

Answer 2

std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

ou qu'en est:

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;

Answer 3

std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);

Answer 4

Cette réponse fonctionne avec C et C ++ et ne nécessite pas STL.

// test if string2 a prefix of string1
// inputs must be non NULL
// returns TRUE if string2 is a prefix, otherwise FALSE

int isAPrefix(const char *string1,
              const char *string2)
{
    return (strncmp(string1, string2, strlen(string2)) == 0);
}

Answer 5

Si vous êtes déjà dépendant Boost, il y a boost::algorithm::starts_with .

int main()
{
    std::cout << boost::algorithm::starts_with("abba", "ab"); // true
    std::cout << boost::algorithm::starts_with("abba", "ba"); // false
    return 0;
}

Chaque fois que vous trouvez std::string manque une méthode de manipulation de chaîne que vous avez besoin, consultez la page Boost bibliothèque String algorithmes.

Answer 6

Utilisez la méthode find d'une chaîne. Vérifiez si l'indice retourne est au début de la chaîne.

Answer 7

http://www.cplusplus.com/reference/string/string/ est un bon endroit pour regarder à travers pour des trucs comme ça. Prenez 10 minutes pour vous familiariser avec ces fonctions, parce que la plupart d'entre eux sont très utiles.

Vous pouvez utiliser trouver pour trouver le texte n'importe où dans l'autre chaîne, mais find_first_of pourrait être plus approprié (et de comparer contre le suffixe). Sinon pour trouver le suffixe, find_last_of serait approprié.

Answer 8

La vraie réponse à votre problème, je pense, utilise un arbre de préfixe. L'algorithme de réponses acceptées fera le travail, mais vous devez vérifier votre mot préfixe wouldbe à tous les autres dans votre jeu de mot qui est linéaire dans le temps. Faites cela pour tous les mots (dites que vous voulez obtenir tous les mots qui sont préfixes à d'autres mots) et vous avez O (n ^ 2) la complexité de vos mains. La simple vérification si un mot est un préfixe à un autre est linéaire sur la longueur du mot.

L'utilisation d'un arbre préfixe répondra à votre première question en temps logarithmique et la seconde - en linéaire. Vérifier si un mot est un préfixe est juste une promenade le long de la place de la racine jusqu'à trouver le mot dans l'arbre et le dernier nœud n'est pas une feuille (ce qui signifie un mot plus étendre existe) - limité par la hauteur de l'arbre. Parcours de l'arbre, d'autre part, et d'écrire le mot en cours sur chaque étape pour laquelle le dernier nœud n'est pas une feuille donnerait une liste de tous les mots de préfixe. Le parcours de l'arbre se fait dans le temps linéaire que vous visiterez chaque nœud une seule fois.

Answer 9

Si vous venez de trouver une chaîne ou sous-chaîne est préfixe autre que u peut simplement utiliser fn

 std::size_t found = str1.find(str2); //returns position of str2 in str1 (if found==0) than it is prefix else not.

Si elle n'existe pas qu'il retourne une valeur d'ordures Si U et faire de même pour un non. des cordes et veulent le faire de manière rapide, vous devez utiliser TRIE.