CODEWITHSUNDEEP
c++
KnowledgeSeeker
KnowledgeSeeker

Reputation: 57

Stack Overflow in rather short (30 lines) program

First of all, I am a beginner, and I don't know what a StackOverflow even is, so please keep your explanations layman-friendly. I read a little about StackOverflow and was surprised that I encountered it even though my program is rather trivial. Anyway, I was practicing in Codewars and then this happened: stackoverflow

The challenge:

You are given two strings. In a single move, you can choose any of them, and delete the first (i.e. leftmost) character.

For Example:

By applying a move to the string "where", the result is the string "here". By applying a move to the string "a", the result is an empty string "". Implement a function that calculates the minimum number of moves that should be performed to make the given strings equal.

Notes Both strings consist of lowercase Latin letters. If the string is already empty, you cannot perform any more delete operations.*/

My code:


void change(std::string & x, std::string & y)
{
    std::string temp = x;
    x = y;
    y = temp;
}

long long shiftLeft(std::string largeString, std::string smallString)
{
  if(largeString.size() < smallString.size())
        change(largeString, smallString); 
    std::string sharedPart;
    int result(0);
    // Find the shared substring in both strings
    for(std::string::size_type i = 0; i < largeString.length(); ++i)
    {
        if(smallString.find(largeString.substr(i, largeString.length() - i)) != std::string::npos)
         {
             sharedPart = largeString.substr(i, largeString.length() - i);
             break;
         }
    }
    
    // If string is empty, return total length of the two strings
    if(sharedPart.empty())
        return largeString.length() + smallString.length();
    
    // Erase strings from the front until they're equal to the shared substring and count the letters erased
    while(largeString != sharedPart)
    {
        largeString.erase(largeString.begin());
        ++result;
    }

    while(smallString != sharedPart)
    {
        smallString.erase(smallString.begin());
        ++result;
    }

    // Return total of letters erased
    return result;

}

Please try to point out my mistake without spoiling the challenge for me.

Upvotes: 0

Views: 150

Answers (1)

kdcode
kdcode

Reputation: 522

Here is the function that does what you state:

size_t challange(const std::string& s1, const std::string& s2)
{
    auto l1 = s1.size();
    auto l2 = s2.size();
    for(size_t ind = 0;;++ind)
    {
        if(ind>=l1||ind>=l2||s1[l1-1-ind]!=s2[l2-1-ind])
        {
            return l1-ind+l2-ind;
        }
    }
}

PS: your challenge would be to figure out how this works :D

Every thread has a region in memory referred to as the stack. The stack is used to implement function calls. It stores return addresses, function parameters and local variables. Excessive use of any of which would result in stack being filled. This situation is called stack overflow. A very deep function call chain, like an endless recursion and very large local variable are common causes of this problem. The code you posted shows non of these. So I guess the problem originates elsewhere. As you mentioned Codewars, the problem may be because some of the test cases of this problem somehow test your function by using it recursively, and your function happens to have a particular error causing the recursion to go forever to at least very deep.

Upvotes: 1

Related Questions