search

AnimeshSinha1309 / algorithms-notebook

The team notebook to keep all template code and notes in.
23 stars 5 forks source link

Fix bug in SuffixArray #18

Closed GaurangTandon closed 4 years ago

GaurangTandon commented 4 years ago

This code failed on input string bababa, as the number of iterations performed was ONE short of what were required to produce the correct result. Normally, I would fix this by using a while (true) loop and checking if rank == n, see example here, but in this case, the size of the matrix was hardcoded to [logn][n] so just increasing logn was sufficient.

AnimeshSinha1309 commented 4 years ago

Did you have the $ placed at the end? It's unlikely there is an error, can you point me to a CodeForces submission where you have that error? The code you have linked is not what we are using now, right, nor the one you have changed it to?

GaurangTandon commented 4 years ago

Sure.

Unchanged code.. The output is:

6 $
5 a$
3 aba$
1 ababa$
4 ba$
0 bababa$
2 baba$

whereas changed code gives the correct output:

6 $
5 a$
3 aba$
1 ababa$
4 ba$
2 baba$
0 bababa$

If you want, can we just tag anurudhp here so that he knows of this bug? (afair you said we are using a template similar to his)