Longest Common Substring Algorithms

Given strings "ABAB" and "BABA"...

A dynamic programming style algorithm constructs a matrix of the substring lengths.

    |   |   | A | B | A | B |
    |   | O | O | O | O | O |
    | B | O | O | 1 | O | 1 |
    | A | O | 1 | 0 | 2 | 0 |
    | B | O | 0 | 2 | 0 | 3 |
    | A | O | 1 | 0 | 3 | 0 |

In this matrix, the 5th column tests the substring ABA of the ABAB sequence. So cell [5, 5] compares ABA to BAB ... the lcs is BA, length 2.

The other approach is to construct a generalized suffix tree for the strings, then find the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

A Simple Suffix Tree Implementation:

Dijkstras Algorithm for shortest path:

Or, here's a more complete implementation.

Function Caching via Memoization

To explain memoization, see these different versions of Fibonacci:

Purely recursive. Highly inefficient. Recalculates every value for every calculation.

Iterative. Much faster.

Here is the memoization technique. A 'cache' dictionary of { (args) : (return_val), } is created. This allows us to quickly locate and reuse any value that has already been calculated.

Here is the same memoization design, implemented as a decorator.

Update Evernote in Wine on Ubuntu

Wine on Ubuntu has problems running the Evernote updates. You get something like: "Evernote was already installed by another user...." The 'find/remove regedit keys' method, described here, and here, did not work for me. I didn't find the reversed the digits in regedit. Well, I only use wine for Evernote. So I used this subtle technique to remove all wine installation. (Don't do this if you have other Wine apps you are keeping.)

sudo apt-get purge wine
rm -rf ~/.wine
sudo apt-get install wine

Then ran the Evernote installer as usual (from files, rt-click on installer).