The solution for the subword pair $(i..j,k..l)$ is stored at $M[adr(i,j),adr(k,l)]$ where $M$ is a two-dimensional matrix of size $(|w|+1)\cdot(|w|+2) / 2$ in both dimensions, and $adr(i,j) = i + (j\cdot(j+1)) \div 2$. This partially eliminates the space loss of the naive strategy – while overlapping subwords still cause space loss (see the holes in the matrix).

Hint: Zoom out with your mouse scroll wheel for bigger word lengths!

Delay: (try 0!)

(note: doesn’t affect a running animation)

Word length: