Crash using aho-corasick algorothm? [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 8 years ago.

I got code for the aho-corasick algorithm here: http://www.komodia.com/aho-corasick .

I used it as the guide said, added lines and built the tree.

I did however change it from using std wstring to std string but that should not matter. I just changed the typedef.

When I use it and search for something, if not results are found there is no problem. When results are found, I get a std out of range exception.

It crashes here:

        if (aIterator==pNode->aMap.end())
            //No, check if we have failure node
            if (!pNode->pFailureNode)
            {
                //No failure node, start at root again
                pNode=&m_aRoot;

                //Reset search string
                sMatchedString="";

                //Did we do a switch?
                if (bSwitch)
                    //We need to do this over
                    --iCount;

                //Exit this loop
                break;
            }
            else
            {
                //What is the depth difference?
                unsigned short usDepth;
                usDepth=pNode->usDepth-pNode->pFailureNode->usDepth-1;

                //This is how many chars to remove
                sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth); //CRASHES HERE!!

                //Go to the failure node
                pNode=pNode->pFailureNode;

                //Set to switch
                bSwitch=true;
            }
        else
        {
            //Add the char
            sMatchedString+=rString[iCount];

            //Save the new node
            pNode=aIterator->second;

            //Exit the loop
            break;
        }
    }

It crashes here:

sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth); 

Here are the variables:

I'm using this to implement censorship in a game.

What could cause it to crash?

I have some strings added twice, could that cause problems?

Thanks

Answer 1

One likely problem is that sMatchedString is "u", while usDepth is 3. This results in a substring from the third character (in a one character string) with length of -2.