Fallback on oneWay scan once the input size is below a certain threshold

[make-github-pseudonymous-again]

Depending on N or N+M? oneWay needs MAX^2 space and D^2 time whereas twoWay needs MAX space and (D^2)/2 time on the first pass, D^2 in total. Current twoWay implementation scans middle snake twice, hence potentially 2 * D^2 total. We have to wait at least until the square root of the input size so that we can reuse pre-allocated memory.

We could also have a twoWay scan that saves the complete history in quadratic space to exploit the potential 1/2 time/space reduction.

Related: #19.

[make-github-pseudonymous-again]

If we want it to stay below linear time we should wait until subproblems are roughly cubic root sized.

[make-github-pseudonymous-again]

Incorrect!

[make-github-pseudonymous-again]

Explicit stack management (#24) allows us to prune the recursion tree at some height and resume rectangle splitting outside Hirschberg's recursion.

[make-github-pseudonymous-again]

To record the entire DP we need space for V that keeps track of progress for each diagonal, as when we only compute the distance, then we need space for additional information

• A bunch of pointers that allow to reconstruct the rectangles in reverse, we just need to store (pointer, x, y, n) or (pointer, x, k, n) tuples to do so since we know rectangles and snakes alternate.
• An array P of the same size as V that stores the current last pointer for each diagonal.

To reconstruct the rectangles we backtrack the pointers. We can either fill a stack to consume later or reverse the direction of pointers while backtracking, so that we can read the information in correct order in a second, forward, pass.

To record these informations, we modify the algorithm so that:

• we create an initial tuple (-1, li, ri, 0) whose address is recorded as the current last pointer of diagonal 0.
• each time V[c] = Math.min(V[c - 1], V[c + 1] - 1) is executed we set the current last pointer of diagonal c to be the current last pointer stored for diagonal c-1 or c+1 depending on which was the min. This allows to know at any point where to look for the top-left corner of the corresponding rectangle.
• each time V[c] = longestCommon***fix(...) updates the value of V[c] we store a new tuple (pointer, x, y, n) where (x,y) is the bottom-right endpoint of the snake, n is the length of the snake, and pointer is the current last pointer of diagonal c. We then update the current last pointer of diagonal c to be the address of this new tuple.

The time complexity is unchanged but the space complexity is now O(MAX + S), where S is the number of snakes in the part of the DP being scanned. Since S <= # traversed diagonals = O(L + D^2) on average inputs but actually much smaller. S is O(MAX^2) since this is the number of times we call longestCommon***fix(...). This is if we start the algorithm without knowing D, but is S = O(D^2) if we set MAX to D (MAX = M + N when we do not know D).

Instead of a one-way scan we can also use a two-way scan. This potentially reduces the amount of explored cells by a factor of two. Also the backward scan does not need a stack or reversing pointers since rectangles come in the correct order. Maybe some usages do not require rectangles to be output in sorted order?

We can simulate a heap on top of already allocated memory (pointers are simply addresses in the allocated memory).