Runtime erro with exit code 6 on online judge

Question

I am doing my c++ homework on an online judge. There are m strings with a length of n. I need to find the minimal expression of a new string, and then insert it in an trie tree. For each string, I need to return the "positon number" of the first identical string.

Following is my code:

#include <cstdio>
using namespace std;

struct trie_node
{
    trie_node * firstSon;
    trie_node * nextBro;
    char value;
    bool isKey;
    int firstPos;
    trie_node(char value):firstSon(NULL), nextBro(NULL), value(value), isKey(false), firstPos(-1){}
};

class trie_Tree
{
public:
    trie_Tree();
    int searchStr(char* desStr, int len, int selfPos);  

private:
    trie_node* searchChar(trie_node* fatherNode, char desChar);
    trie_node* root;
};

trie_Tree::trie_Tree()
{
    root = new trie_node('0');
}

int trie_Tree::searchStr(char * desStr, int len, int selfPos)
{
    trie_node* fatherNode = root;
    for (int i=0; i<len; i++)
    {
        fatherNode = searchChar(fatherNode, desStr[i]);
    }
    if (!fatherNode->isKey)
    {
        fatherNode->isKey=true;
        fatherNode->firstPos=selfPos;
    }
    return fatherNode->firstPos;
}

trie_node* trie_Tree::searchChar(trie_node* fatherNode, char desChar)
{
    if (fatherNode->firstSon==NULL)
    {
        fatherNode->firstSon = new trie_node(desChar);
        return fatherNode->firstSon;
    }

    trie_node* travNode = fatherNode->firstSon;
    while (travNode->nextBro!=NULL)
    {
        if (travNode->value==desChar) return travNode;
        travNode=travNode->nextBro;
    }

    if (travNode->value==desChar) return travNode;
    else
    {
        travNode->nextBro = new trie_node(desChar);
        return travNode->nextBro;
    }
}

char* getMinPre(char *s, int _size)
{
    int min=0, trav=1;
    while (trav<_size && min<_size)
    {
        int i;
        for (i=0; i<_size; i++)
        {
            if (s[(min+i)%_size]<s[(trav+i)%_size])
            {
                trav=trav+i+1;
                break;
            }
            else if (s[(min+i)%_size]>s[(trav+i)%_size])
            {
                min=trav;
                trav=trav+1;
                break;
            }
        }
        if (i==_size) break;
    }

    char * result=new char[_size];
    for (int i=0; i<_size; i++)
    {
        result[i]=s[(min+i)%_size];
    }
    return result;
}

int main()
{
    int m, n, result=0;
    scanf("%d %d", &m, &n);

    trie_Tree tt=trie_Tree();

    char* s=new char[n+1];
    for (int i=0; i<m; i++)
    {
        scanf("%s", s);
        s=getMinPre(s, n);
        result = tt.searchStr(s, n, i);
        printf("%d\n", result);
    }
    delete[] s;

    return 0;
}

I compiled my code with VS and g++, and runned my program lots of times for testing. It worked perfectly.

But when the online judge system returned runtime error(exitcode 6).

I googled "exit code 6". It is raised by the program itself, e.g. by making the abort() system call. It can be caused by new and delete operation. But I still cannot debug my code.

Anyone can help me?

Answer 1

That's a lot of code, but some things to look into:

1. Inside your main function you allocate s: char* s=new char[n+1];.
2. You pass s into char* getMinPre(char *s, int _size).
3. getMinPre allocates another buffer, and returns it, overwriting s: s=getMinPre(s, n); (memory leak of initial s buffer).

This potentially happens a lot in the main function's loop, hence you may run out of memory. (getMinPre allocating and overwriting the pointer to allocated buffer).

Since this is an online judge platform, I'd recommend coming up with extreme test cases (min, max elements, tons of iterations) and running them locally.

Also: add some debug information. You can even encapsulate them within #ifdef so you won't have to remove them.