Longest Common Substring: from Brute Force to Sparse DP
I wrote an explanation about a sparse dynamic programming (DP) algorithm, that I have developed, for longest common substring (not subsequence!). I follow the roadmap:
basic intuitions -> brute force -> DP -> sparse DP
Hopefully, it is of educational value. This is the link to the github repo:
https://github.com/O-logN/SparseDP-LCSubstr
the explanation is in the github page.
About complexity
This sparse DP algoritm is an "evolution" of a DP algorithm that is sometimes found on the internet. It requires O(n + m + #(x,y)) time and O(min(n,m)) space, given two strings x and y of length n and m respectively, where #(x,y) denotes the number of index pairs (i,j) such that x[i]=y[j].
In the github page, i also mention two further optimizations.
Help with benchmarks (check the github page intro) would be appreciated.