Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences

Kang Ning, Kwok Pui Choi

The Longest Common Subsequence (LCS) problem is a very important problem in math- ematics, which has a broad application in scheduling problems, physics and bioinformatics. It is k…