Is comparing string sizes an acceptable alternative to comparing characters?

I am writing a grep function in C ++ (as a standalone exercise - I realize this does not have the actual grep function) to take the original string and the search string you are looking for. In the code, I enter all the characters in the grep line up to the first place it sees. Then I compare the characters in the grep string with the search string and if it matches, store it in the temp string. I loop over the grep string and compare the length of the search string with the temp string to see if it matches.

My question is, is this bad shape when comparing lengths? I could use a for loop to compare each individual character to each other, but it looks like it will quote CPU cycles frequently. Here is my input function for reference:

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;
}

      

0


a source to share


2 answers


No, not a bad shape at all. After all, in at least some senses, two strings cannot be equal unless they are of the same length.



For a really good time, take a look at the Boyer-Moore string matching algorithm and the Knuth-Pratt-Morris algorithm. J [sic! He really says so] Moore has a nice page on them.

+4


a source


If you are using std :: string the STL search functions will probably work more efficiently than this version you created. Finding a substring string is a known issue and I'm pretty sure the library version is optimized the way it can be.



0


a source







All Articles