backo's blog

g++ runtime error
By backo, history, 8 years ago, In English

Hello everyone!

Here we go again.. writing a solution to a problem which supposedly works on my PC but delivers runtime error on the codeforces server.

The submission I'm talking about is this: 19567131. I've been reading about suffix trees and trying to solve a simple problem. The solution is pretty lengthy, but... Does anyone know what error code 255 is? I also tried custom tests and occasionally I get error code -1073741819. I compile under gcc 5.1.0 — the same as codeforces I think, using c++11. I tried using flags "-std=c++11 -Wextra -pedantic -Wall -O2" but didn't get anything interesting. I've been playing around with this for quite a while now, but I can't seem to get it to work.

I'd be grateful for any help anyone can provide!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

At least one of the problems is that you don't zero-initialize your child array.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This is what crashed my application, thanks alot!

    However, now I'm getting memory limit exceeded (19572966). I'm guessing memory leak, and I've managed to fix it somewhat by reducing alphabet size and adding delete on some parts of the code but I'm still getting MLE, this time on test 51 (19573167). Also, the code is getting pretty close to the time limit as well...

    Theory says that there shouldn't be more than 2m nodes in the suffix tree so if I'm calculating correctly, it should pass for memory limit. Also, the algorithm should be O(m) which should be pretty fast..

    This means there must be something wrong with my code, I'll keep trying

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
class Active { //SuffixTree::Active
	public:
		int edge,length;
		SuffixNode* node;
		Active() : node(nullptr),edge(-1),length(0) {}
};
  • In constructor 'SuffixTree::Active::Active()':
  • main.cpp|46|warning: 'SuffixTree::Active::node' will be initialized after [-Wreorder]|``
  • main.cpp|45|warning: 'int SuffixTree::Active::edge' [-Wreorder]|
  • main.cpp|47|warning: when initialized here [-Wreorder]|

I think it might be this way:

class Active {
	public:
                SuffixNode* node;
		int edge,length;
		Active() : node(nullptr),edge(-1),length(0) {}
};

root->child[Input(i)] = new SuffixNode(i,&end);
  • main.cpp||In member function 'void SuffixTree::build()':|
  • main.cpp|74|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp|82|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp|105|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp|106|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp|108|warning: array subscript has type 'char' [-Wchar-subscripts]|
SuffixNode* selectNode(int i) {
	return active.node->child[Input(i)];
}
  • main.cpp||In member function 'SuffixTree::SuffixNode* SuffixTree::selectNode(int)':|
  • main.cpp|123|warning: array subscript has type 'char' [-Wchar-subscripts]|

All other warnings are about using chars as SuffixNode ans vice versa

  • main.cpp||In member function 'char SuffixTree::nextChar(int)':|
  • main.cpp|130|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp|132|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp||In member function 'void SuffixTree::walkDown(int)':|
  • main.cpp|149|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp||In function 'void recc(SuffixTree::SuffixNode*, int, int, Sol*)':|
  • main.cpp|184|warning: array subscript has type 'char' [-Wchar-subscripts]|
  • main.cpp||In function 'int main()':|
  • main.cpp|201|warning: array subscript has type 'char' [-Wchar-subscripts]|

Hope it help :3

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've already seen these errors but I don't think it matters if I use char as index. Same for this initializer order (though I fixed that one)

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Debugger also said that program crashes on line 70

active.edge = selectNode(i)->start;

You should check it when global var SuffixTree tree initialized

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes! This combined with slycelotes comment really helped. Turned out the child[] array wasn't initialized to nullptr so the if(..child[i]!=nullptr) passes even though there's no SuffixNode object there.

    → Reply