Finding the longest common subsequence

One way to compare string similarity is by finding their longest common subsequence. This is useful in finding differences between mutations of data such as source code or genome sequences.

A subsequence of a string is the same string with zero or more of the indices removed. So, some possible subsequences of "BITCOIN" could be "ITCOIN", "TON", "BIN", or even "BITCOIN" itself, as shown in the following figure:

The longest common subsequence is exactly what it sounds like. It is the longest subsequence common to both strings. For example, the longest common subsequence of "find the lights" and "there are four lights" is "the lights."

Getting ready

Install the data-memocombinators package from Cabal. This allows us to minimize redundant computations to improve runtime as follows:

$ cabal install data-memocombinators

How to do it...

1. The only import we will need is this handy package to easily support memoization:

   import qualified Data.MemoCombinators as Memo...