Crash using aho-corasick algorothm?

Question

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.