La comparaison des tailles de chaînes est-elle une alternative acceptable à la comparaison de caractères?

Question

J'écris une fonction grep en C++ (comme un exercice auto-assigné - je réalise que cela n'a pas la fonctionnalité d'une fonction grep réelle) pour prendre une chaîne d'origine et la chaîne de recherche que vous recherchez. Dans le code, j'entre tous les caractères dans une chaîne grep jusqu'au premier espace qu'il voit. Ensuite, je compare les caractères de la chaîne grep avec la chaîne de recherche, et si elle correspond, stockez-la dans une chaîne temporaire. Je boucle sur la chaîne grep et compare la longueur de la chaîne de recherche avec la chaîne temporaire pour voir si elle correspond.

Ma question: est-ce une mauvaise forme, en comparant les longueurs? Je pourrais utiliser une boucle for pour comparer chaque caractère individuel l'un par rapport à l'autre, mais cela semble comme il mange des cycles CPU sans nécessité. Voici ma fonction d'entrée pour la référence:

std::string grep(std::string originalStr, std::string searchStr) 
{ 
std::string grepStr = ""; 
std::string finalStr = ""; 
//stores final string; is the return value 
finalStr.resize(originalStr.length() + 1); 
grepStr.resize(originalStr.length() + 1); 

int place = 0; 
//remember where you are in originalStr[place] 
int numOfOccurences = 0; 
//remember number of times searchStr was found; 
//not necessary 
std::string tempStr = ""; 
//will temporarily hold grepStr  

//handles case if first occurence is a space 
if (originalStr[0] == ' ') 
{ 
    place++; 
} 

while (place != originalStr.length()) 
{ 
    tempStr = ""; 

    while (originalStr[place] != ' ') 
    { 

     if (originalStr[place] == ' ') 
     { 
      break; 
     } 

     grepStr[place] = originalStr[place]; 
     ++place; 
    } 

    ++place;//ensures you skip over the space next pass 

    for (int i = 0; i != grepStr.length(); i++) 
    { 
     if (grepStr[i] == searchStr[i]) 
     { 
      //if they are the same, append that char.. 
      tempStr[i] = grepStr[i]; 

      if (tempStr.length() == grepStr.length()) 
      //..then check for string length; if same, searchStr equals tempStr 
      //and you can append grepStr to the finalStr 
      {      
       for (int x = 0; x != finalStr.length(); x++) 
       { 
        finalStr[x] = grepStr[x]; 
       } 

       ++numOfOccurences; 
       //add one to the number of occurences in originalStr 
       finalStr += ' '; 
       //add a space IF you find the string 
      } 
     } 
    } 
} 

return finalStr; 
} 

Answer 1

Non, pas mal du tout. Après tout, au moins dans certains sens, deux chaînes ne peuvent pas être égales si elles n'ont pas la même longueur.

Pour passer un très bon moment, jetez un œil à l'algorithme d'appariement de cordes de Boyer-Moore et à l'algorithme de Knuth-Pratt-Morris. J [sic! Il le dit vraiment de cette façon] Moore a un nice page sur eux.

Answer 2

Si vous utilisez std :: string, les fonctions de recherche STL fonctionneront probablement plus efficacement que cette version que vous avez créée. La recherche d'une sous-chaîne dans une chaîne est un problème connu et je suis sûr que la version de la bibliothèque est aussi optimisée que possible.