Is there an alternative to using str.substr( ) to extract a substring at a given position?

Question

I am trying to compare two std::strings, and decide if string A is the same as string B, but with the insertion or deletion of a single character. Otherwise it returns false. For example: "start" and "strt" or "ad" and "add" Currently:

if(((sizeA - sizeB) != 1)
   && ((sizeB - sizeA) != 1))
{
    return false;
}

if(sizeA < sizeB)
{
    for(int i = 0; i < sizeA; ++i)
    {
        if(stringA[i] != stringB[i])
        {
            if(stringA.substr(i)
               == stringB.substr(i + 1))
            {
                return true;
            }
            else return false;
        }
    }
} //with another loop that runs only if stringA is larger than stringB

This works flawlessly, but gprof tells me that this function is being bogged down. I tried converting the for loop to use iterators to access the chars, but this doubled my run time. Ive narrowed it down to my use of std::string.substr( ) because it is constructing new strings each time stringA and stringB differ in size by 1.

When the first character differs, I need a more efficient way to check if I were to delete that character, would the two strings then be equal?

Answer 1

It seems, once it is known whether there is a one character difference the comparison can be done more effective with a single pass over the string: find the location of the difference, skip the character, and see if the tail is the same. To that end it is obviously necessary to know which one is the smaller string but that's trivial to determine:

bool oneCharDiff(std::string const& shorter, std::string const& longer) {
    if (shorter.size() + 1u != longer.size() {
        return false;
    }
    typedef std::string::const_iterator const_iterator;
    std::pair<const_iterator, const_iterator> p
        = std::mismatch(shorter.begin(), shorter.end(), longer.begin());
    return std::equal(p.first, shorter.end(), p.second + 1);
}
bool atMostOneCharDiff(std::string const& s0, std::string const& s1) {
    if (s0.size() < s1.size()) {
        return oneCharDiff(s0, s1);
    else if (s1.size() < s0.size()) {
        return oneCharDiff(s1, s0);
    }
    else {
        return s0 == s1;
    }
}

Answer 2

Try:

if (stringA.compare(i, stringA.npos, stringB, i+1, stringB.npos) == 0) {
  /* the strings are equal */
}

In this write-up, that's version (3) of std::basic_string::compare.